p-adic integer

Take the natural numbers (or the integers; as we'll see, it doesn't matter). Instead of the "usual" metric d(x,y)=|x-y| using the absolute value, fix some prime number p and take d(x,y)=|x-y|_p using the p-adic norm. The p-adic integers are the completion Z_p of this metric space.

Which probably means nothing to you, unless you eat metrics for breakfast. Go to the algebraists, and you'll hear some mumbling about the reverse limit of sequence

Z/(p⋅Z), Z/(p²⋅Z), Z/(p³⋅Z), ...,

which probably means something, but I'm not sure what. So here's a direct "construction".

Take the natural numbers in base p. Now make each number a leftwards infinite string of digits. How? Well, consider the number 1, written "1" to base p. We could equally well write it "01" or "001" or "000000000001". So let's tag on an infinite string of 0's, and write down "...0001". Obviously, we can tag this infinite string of 0's on to every natural number, so we consider all natural numbers as such infinite strings.

What if we pick some other string of digits? Obviously, "...d₃d₂d₁d₀" won't correspond to any natural number. But if we try to write it down as

∑_kd_kp^k

then it makes sense as a "p-adic number" (in analysis terms, the series is a Cauchy series in the p-adic norm, so it converges in the completion; the completion of Z in the p-adic norm is the set described here).

Note that we can give exact algorithms for adding and multiplying two such "numbers": just follow the normal algorithms for working with base-p natural numbers! Of course the algorithms never terminate, because you now have an infinite number of digits. But here's the clincher: to determine the k'th digit of any result, only digits 0,...,k of the two operands need to be considered! So the k'th digit is determined by a finite procedure. We have an algorithm for performing approximate p-adic arithmetic.

This is even better than the real numbers! For reals, no amount of digits is necessarily sufficient to determine any digit of the result (consider adding 0.9999... to 0.0000...; the result could be <1 no matter what finite number of digits you consider: if the first 100 digits are all 9's and 0's, digit 101 could still be 7 and 1, leading to a <1 result).

As an example, let's take p=3 and see what ...222 really is. Well, one way to discover is to try to add 1=...001 to it. We perform grade school addition. Immediately we discover the first (one's) digit is 0 (since 2+1=10₃, and only these 2 digits affect the first digit). Now we carry the 1, and add 1+2+0 to discover the second digit; again we get a 0 and carry a 1. So we could write the sum:

carry    ...111111
  A       ...222222
  B     + ...000001
        -----------
          ...000000

and we see that ...2222+...0001=0, so that ...2222 is really -1.

Cool. It turns out that the p-adic integers really are a ring, and that they contain the integers. But not just!

We can perform long division to determine 1/b for any b not divisible by p. For instance, we can determine the 3-adic representation of 1/5.

Well, 5=...00012₃. And if x=1/5, then 5*x=1. So the 1's digit of 1/5 must give a 1's digit of 1 when multiplied by 2 (the 1's digit of 5), so 1/5=...2. The 3's digit must come out 0, so the 3's digit of 1/5 is 0 (note that 12*2=101₃). This means the 9's digit must be 1 (12*102=2001₃), the 27's digit must be 2, and the 81's a 1. After this, it settles down, and

1/5 = ...1210121012102

(an infinite repeated "1210" block).

If b is divisible by p, it turns out not to have an inverse 1/b. And even nicer, whenever 1/b exists, it has a repeating p-adic expansion (just like the "real" rational numbers). This is true even if b isn't a regular integer; we can divide by b iff its first (rightmost!) digit isn't "0".

A common case is p=2. 2-adics are exactly like 2's complement, only with an "infinite" word size; as above "...111" is -1, which may help make some sense of things.

We sometimes find more exotic "numbers". For instance, in the 5-adics (and generally iff p=4k+1) we can find a square root of -1=...444!

In base 5:

2*2 = 4
12*12 = 144
212*212 = 100444
1212*1212 = 2024444
31212*31212 = 2040344444
...

so sqrt(-1) (in 5-adics) is ...31212. You can find more digits using any of the standard techniques for finding square roots; the Babylonian square root algorithm is recommended (note that you know how to divide by 2 in the 5-adics -- just multiply by 1/2!)

---

Archimedes Plutonium is somewhat notorious for his claims that the "p-adics" are the "real" natural numbers (and everything else a fakery). In fact, he takes the 10-adics, which (p not being prime!) are even stranger than p-adics (not only 1/10, but also 1/2 and 1/5 don't exist there). He doesn't seem to realise that the precise structure you get heavily depends on p.

What is true, however, is that in p-adic integers you can find "counterexamples" to Fermat's last theorem. Which is not surprising, as it deals with integers, not with other objects.