Padic numbers are an alternative to the reals. They have real applications, but playing with padics is also math geek fun.
I’m a guy who spends a lot of time in abstract mathland. I love math, and one of my passions is trying to take the beautiful abstractions of math, and explain them in ways that make them at least a little bit comprehensible to people who don’t spend as much time with their heads in the clouds as I do.
When someone says “math,” what you probably think of is numbers. Math is actually a lot more than numbers—but even when we’re dealing with something as common and everyday as numbers, there are different ways of looking at things that are both fascinating and strange.
Everyone is familiar with the idea of the real numbers. The real numbers are part of a progression of types of numbers. In math, we generally start with the natural numbers—that’s 0, 1, 2, and so on. Then we expand the range of values we can describe by adding negative numbers, which gives us integers. Then we allow ratios of two different numbers, which gives us fractions. Finally, we add irrational numbers, and we get the reals.
Padics are an alternative (in fact, the only real alternative!) to the real numbers. Instead of going from the rationals to the reals, we can go from the rationals to the padic numbers.
A Real Alternative
There’s a reason why we couldn’t stop at the rational numbers, why we needed to keep going and add another class of numbers. When you look at the class all of the possible rational numbers, you find that there are gaps—places where we know that there must be a number, and yet, if we limit ourselves to fractions, there isn’t anything to fit.
For example, we know that there must be some number such that if we multiply it by itself, the result is 2. That number is almost 1 4/10ths, but that’s off by about 1/100th. We can try 141/100, but that’s not quite right either: it’s off by about 4/1000. That’s still not quite right—our refined estimate is now off by about 2/10,000. No matter how far we go, no fraction is ever quite right. There are fractions that are just a tiny, miniscule bit too small, and there are fractions that are a tiny miniscule bit too big, but there’s no fraction that’s exactly the right number.
That number, which we call the square root of two, fits into a gap in the rational numbers. It’s not a rational number, but we know that there’s a number there! If we look at those gaps carefully, we’ll find that most numbers are actually in those gaps! The real numbers and the padics are both ways of creating number systems that allow us to define the numbers that fit in to those gaps.
The easiest way to understand padic numbers is think about how we represent real numbers in basep. In real numbers, we represent them using the powers of the base. So, for example, in base 10, when we write 123, what we mean is 1 * 10^{2} + 2*10^{1} + 3*10^{0}. We can do the same thing with other number bases—so, for example, in base 5, if we wrote 24.31, that would mean 2*5^{1} + 4*5^{0} + 3*5^{1} + 1*5^{2}—or, in the familiar base10, 14.64.
Using our normal notation for real numbers, we fill in the gaps between the rational numbers by writing numbers as an integer part, followed by a decimal point, followed by a fractional part. For real numbers that aren’t rationals, we say that the fractional part goes on forever. So the square root of two starts 1.4142135624, and continues on and on, forever, without repeating. That gives us the real numbers. In that system, every number can be written using a finite number of digits to the left of the decimal point, and an infinite number of digits to the right.
Padic numbers are exactly the opposite: every padic number has a finite number of digits to the right of the decimal, but it can have an infinite number to the left!
Defining a Padic Number System
Defining a system of padic numbers starts off being pretty similar to how we compute the representation of numbers in a standard numeric base. We need to pick a prime number, p as the base of our system—that’s the p in padic. So base7 in padic is called 7adic numbers.
To express a number n in base 7, take n modulo 7. That’s the rightmost digit of your number. Divide by 7, dropping the fractional part, and take the result modulo 7, and that’s the secondrightmost digit. Continue this until there’s nothing left.
For example, take the number 222 in base10. If we wanted to represent that in base7, we’d do:

If we divide 222 by 7, we get 31 with a remainder of 5. So the rightmost digit is 5.

We take 31, and divide it by 7, giving us 4, with a remainder of 3. So the second digit is 3.

We’re left with 4, so the last digit is 4.
So—222 in base7 is 435. Well, it’s the same in 7adic. For a particular base B, all positive integers are written the same in both baseB and Badic. Integer arithmetic that doesn’t involve negative numbers is also the same.
There’s one really big catch that’s a bit of a mindblower for most people. If you’re used to the real numbers, you know that 35 in base 10 and 43 in base8 are the same number—they’re just different representations. But in padic numbers, each possible p creates a whole different system of numbers! 35 in 10adic is not the same number as 43 in 8adic. As we’ll see when we get to metrics, they’re quite different. Each padic base produces a distinct system of padic numbers, and you can’t convert between them as freely as you can in the conventional reals. Decimal notation and hexidecimal notation are just different ways of writing numbers in the same number system; 2adic and 3adic are different number systems!
Doing Arithmetic in Padic
The first essential difference between padic numbers and the reals comes when you try to do arithmetic.
As I said earlier, for integers, if you don’t do anything with negative numbers, padic arithmetic is the same as real number integer arithmetic. In fact, if you’re working with padic numbers, there are no negative numbers at all! In a padic number system, subtracting 1 from 0 doesn’t give you 1. It “rolls over” like an infinite odometer. So for 7adic, 01 = ...666666666! That means that arithmetic gets a bit different. Actually, it’s really pretty easy: you just do arithmetic from the right to the left, exactly the way that you’re used to.
For addition and subtraction, padic works almost like normal realnumber arithmetic using decimals. Addition is basically what you know from decimal arithmetic. Just go right to left, adding digits, and carrying to the left.
So, for example, in 5adic, if you have a number ...33333, and 24, to add them, you’d go through the following steps.

3 + 4 is 7, which is 12 in base5. So the first digit of the sum is 2, and we carry 1.

3 + 2 is 5, plus the carried 1 is 6—so again, 12 in base5. So the second digit is also 2, and we carry 1.

3 + 0 is 3, plus the carried 1 is 4, so the third digit is 4.

For all the rest of the infinite digits streaming off to the left, it’s 3 + 0 = 3.
So the sum is ...3333422.
To do subtraction, it’s still basically the same as what you’re used to from reals. There’s just one simple change: infinite borrowing. In normal subtraction, you can borrow from the position to your left if there’s anything to your left to borrow from. For example, in decimal, if you wanted to subtract 9 from 23, you’d borrow 10 from the 2, then subtract 9 from 13, giving you a result of 14. But if you wanted to substract 39, you couldn’t borrow, because there’s nothing to the left to borrow from. In padic, you can always borrow. If you’re subtracting 39 in 10adic, then you can borrow from the 0 to the left of the 3. Of course, there’s nothing there—so it needs to borrow from its left. And so on—giving you an infinite string of 9s. So 39 in 10adic gives you ....999999994.
Let’s do a full example: ...33333  42 in 5adic.

As always, we start from the right. 3  2 = 1, so the first digit is 1.

Since 3 is smaller than 4, we need to borrow 1—so we have 13 base 5, which is 8. 8  4 = 4. So the second digit is 4.

For the third digit, we just subtract the borrowed 1, so it’s 2.
So the result is ...3333241.
It Gets Stranger
Multiplication and division get even stranger in padic. Because we can’t have an infinite number of digits to the right of the decimal, padic ends up representing fractions using infinite numbers of digits on the left of the decimal. And that means that we get collisions between fractions and negative numbers. (This should start to give you a clue why each padic base is really a different number system: the correspondance between rollover negatives and infinitely long fractions is different in each base.) It’s easiest to see how this works by looking at a concrete example.
The fraction 1/3 can’t be written as finitelength string in base5. In 5adic, that means we can’t write it using digits to the right of the decimal point—we would need an infinite number of digits, and we’re not allowed to do that. Instead, we need to write it with an infinite number of digits to the left! 1/3 in 5adic is: ...1313132.
Looks crazy, but it does work: if you do a tabular multiplication, right to left, multiplying ...1313132 by 3 gives you one! Let’s work it through:

Start from the right: the rightmost digit is 2. 3*2 is 6, which is 11 in base 5; so the rightmost digit is 1, and you carry a one.

The next digit is 3: 3 times 3 is—9, plus the carried 1, gives 10—which is 20 in base5, so the next digit is a 0, and you carry 2.

The next digit is 1: 3*1 is 3 plus the carried 2 = 5; so 0, carry 1.
And so on—the rest are zeroes, so ....13131313132 * 3 = 1, so ....131313132 == 1/3 in 5adic.
OK, we’ve shown that ....131313132 is 1/3 because we get 1 when we multiply it by 3, but how can we actually compute this value of 1/3? Just like we do with decimal real numbers: by division.
Division in padics is actually easy. The trick is that like all of the other arithmetic, it goes from right to left. Suppose we want to divide N by M. To make it clear, we’ll talk about the digits of M and N using subscripts, so the rightmost digit of a number X is X_{1}; the secondrightmost is X_{2}, etc. The multiplication algorithm is:

Start at the rightmost digit of both numbers.

Find the smallest number d which, multiplied by M, has N_{i} as its rightmost digit.

Subtract d*M_{i} from N.

Drop the trailing last digits from N, giving N'.

Now divide N' by M, and put d on the right.
Let’s walk through 1/3 in 5adic:

The rightmost digit of 1 is 1.

What, multiplied by 3 will have a trailing digit of 1 in base5? 2*3=6, which is 11 in base5. So d = 2.

Now we subtract the “11” from 1—which is really ...00001. So it becomes ...444440.

We drop the trailing 0, and N' is ...4444.

So now we divide ...4444 by 3. What’s the smallest number which, multiplied by 3, ends in a 4 in base5? 3*3=9, which is 14 in base5. So the next digit of the result is 3.

Now, we subtract 14 from ...4444. That gives us ...44430. Drop the zero, and it’s ...4443

Next digit is a 1, leaving ...444
Crazy, huh? There is one catch about division: it only really works if the pbase in your padic system is a prime number. Otherwise, you get into trouble, because your padic system of numbers isn’t a field if p is nonprime.
Although it takes getting used to, arithmetic with the padics is actually simpler than it is with conventional real numbers. Everything goes right to left. It’s all more uniform. In fact, padic has been seriously proposed as a number representation for computer hardware, because the hardware is much easier to build when everything can be done uniformly right to left!
The Power of Padic Metrics
So that’s the basics of arithmetic. But what makes padic numbers really interesting and valuable is metrics.
Metrics are one of those ideas that are simultaneously simple and astonishingly complicated. The basic concept of a metric is straightforward: I’ve got two numbers, and I want to know how far apart they are. But it turns out that there are many different ways of defining “how far apart” things are. Our common notion comes from our geometric intuition. In math, though, you can’t ever just rely on intuition: you need to be able to define things precisely. And precisely defining a metric is difficult. It’s also fascinating: you can create the real numbers from the integers and rationals by defining a metric, and the metric will reveal the gaps between the rationals. Completing the metric—filling in those gaps—gives you the real numbers. Or, if you fill them in differently, the padic numbers.
To define just what a metric is, we need to start with fields and norms. A field is an abstract algebraic structure that describes the behavior of numbers. It’s an abstract way of talking about the basic structure of numbers with addition and multiplication operations.
A norm is a generalization of the concept of absolute value. If you’ve got a field F, then a norm of F is a function  x  from values in F to nonnegative numbers, with the following properties:

 x  = 0 if and only if x = 0.

x y = x y

x + y <= x + y
A norm on F can be used to define a distance metric d(x, y) between x and y in F as  x  y.
For example, the absolute value is clearly a norm over the real numbers, and it defines the Euclidean distance between them.
Using the norm, we can see where the gaps between the rational numbers come from.
You can define a sequence a of values in F as a = { a_{i} } for some set of values i. There’s a special kind of sequence called a Cauchy sequence, which is a sequence where lim_{i,j > infinity} a_{n}  a_{m} = 0.
You can show that any Cauchy sequence converges to a real number. But even if every element of a Cauchy sequence is a rational number, it’s pretty easy to show that many (in fact, most!) Cauchy sequences do not converge to rational numbers. There’s something in between the rational numbers which Cauchy sequences of rational numbers can converge to, but it’s not a rational number. When we talk about the gaps in the rational numbers, that’s what we mean. (Yes, I’m handwaving a bit, but getting into the details would be a distraction, and this is the basic idea!)
When you’re playing with number fields, the fundamental choice that you get is just how to fill in those gaps. If you fill them in using a metric based on a Euclidean norm, you get the real numbers. What makes the padic numbers is just a different norm, which defines a different metric.
The idea of the padic metric is that there’s another way of describing the distance between numbers. We’re used to thinking about distance measured like a ruler on a numberline, which is what gives us the reals. For the padics, we’re going to define distance in a different way, based on the structure of numbers. The way that the padic metric works is based on how a number is built relative to the primenumber base.
We define the padic metric in terms of the padic norm exactly the way that we defined Euclidean distance in terms of the absolute value norm. For the padic number, we start off with a norm on the integers, and then generalize it. In the padic integers, the norm of a number is based around the largest power of the base that’s a factor of that number: for an integer x, if p^{n} is the largest power of p that’s a factor of x, then the the padic norm of x (written x_{p}) is p^{n}. So the more times you multiply a number by the padic base, the smaller the padic norm of that number is.
The way we apply that to the rationals is to extend the definition of pfactoring: if p is our padic base, then we can define the padic norm of a rational number as:

0_{p} = 0

For other rational numbers x: x_{p} = p to the ord_{p}(x) power where:


If x is a natural number, then ord _{p}(x) is the exponent of the largest power of p that divides x.

If x is a rational number a/b, then ord _{p}(a/b) = ord _{p}(a)  ord _{p}(b).

Another way of saying that is based on a property of rational numbers and primes. For any prime number p, you can take any rational number x, and represent it as a pbased ratio p^{n*(a/b)}, where neither a nor b is divisible by p. That representation is unique—there’s only one possible set of values for a, b, and n where that’s true. In that case, the padic norm of x, x_{p} == p^{n}.
Ok, that’s a nice definition, but what on earth does it mean?
Two padic numbers x and y are close together if x  y is divisible by a large power of p.
In effect, this is the exact opposite of what we’re used to. In the real numbers written out in decimal for as a series of digits, the metric says that the more digits numbers have in common moving from left to right, the closer together they are. So 9999 and 9998 are closer than 9999 and 9988.
But with padic numbers, it doesn’t work that way. The padic numbers are closer together if, moving right to left, they have a common prefix. The distance ends up looking very strange. In 7adic, the distance between 56666 and 66666 is smaller than the distance between 66665 and 66666!
As strange as it looks, it does make a peculiar kind of sense. The padic distance is measuring a valuable and meaningful kind of distance between numbers—their distance in terms of their relationship to the base prime number p. That leads to a lot of interesting stuff, much of which is, to be honest, well beyond my comprehension. For example, the Wiles proof of Fermat’s last theorem uses properties of the padic metric!
Mark ChuCarroll is a PhD computer scientist and professional software engineer. He works as a server engineer at foursquare. His professional interests include collaborative software development, programming languages and tools, and how to improve the daily lives of software developers. Mark blogs about math related topics on Scientopia. Aside from general geekery and blogging, he plays classical music on the clarinet, traditional Irish music on the wooden flute, and folds elaborate structures out of paper.
Send the author your feedback or discuss the article in the magazine forum.