p-adic Numbers

Consider the following sequence of calculations:
7 * 3 = 21
7 * 43 = 301
7 * 143 = 1001
7 * 7143 = 50001
Roughly speaking, the p-adic numbers arise when we continue this sequence to infinity, and say that the second term on the left hand side of the equation is 1/7.
7 * ...7143 = ...0001
1/7 = ...7143
To make the maths work, there are a couple more things we need:

The p-adic valuation, p-adic norm, and p-adic metric

The p-adic valuation on integers is defined as
ordp a = the highest power of p which divides a,
for example, ord5 50 = 2.

The p-adic norm on integers is defined as
normp a = 1 / p ^ ordp a,
for example, norm5 50 = 1/25.

The p-adic metric on integers is defined as
dp (x,y) = normp (x-y),
for example, d5 (7,57) = 1/25.

So, forgetting for a moment that p is meant to be a prime, we see that if we continue the sequence ...7143 in the "10-adics", we can get arbitrarily close to 1/7.

The p-adic integers, Zp

Let's start writing our numbers the other way round. Instead of ...7143, we will write 3 + 4.10 + 1.10^2 + 7.10^3 + O(10^4). We'll call 3, 4, 1, 7 the coefficients of this number. For ordinary integers, the coefficients stop at some point - or rather, they are all zero after a certain point. If we allow the coefficients to be infinite sequences, we get the p-adic integers, Zp.

Mathematically, this is analogous to the way that the reals are constructed as the completion of the rationals, by "filling the holes" where a Cauchy sequence over the rationals does not have a limit in the rationals. The p-adic integers are the completion of the integers using Cauchy sequences relative to the p-adic metric.
Consider the sequence 1, 1.4, 1.41, 1.414, 1.4142, etc. Each of the terms is rational. But the number to which they are tending (sqrt 2) is not. We get the reals by allowing the decimal places to go on forever. Notice that as the sequence continues, the places are getting smaller and smaller: 1 > 0.4 > 0.01 > 0.004 > 0.0002 etc.
Well, the construction of the p-adic integers is exactly analogous. We have a sequence 3, 43, 143, 7143, and we allow it to go on forever. Notice how, according to the p-adic metric,, the places are getting smaller and smaller: 3 >p 40 >p 100 >p 7000.

Our Haskell code allows us to experiment:
printQp (recip (toQp 10 7)) returns 3*10^0 + 4*10^1 + 1*10^2 + 7*10^3 + 5*10^4 + 8*10^5 + 2*10^6 + 4*10^7 + 1*10^8 + 7*10^9 + 5*10^10 + 8*10^11 + 2*10^12 + 4*10^13 + 1*10^14 + 7*10^15 + O(10^16)
printQp is the pretty print function. It's a bit cumbersome, so usually we don't bother, and just write
recip (toQp 10 7), which returns Qp 10^0 [3,4,1,7,5,8,2,4,1,7,5,8,2,4,1,7]
(I'll explain about Qp below, but first let's notice a couple more things about Zp.)

One handy feature of the p-adic integers is that we don't need minus signs. If we type
-(toQp 10 7), we get Qp 10^0 [3,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
(Addition in Zp is carried out the same way as in Z, except that because we are writing the numbers "backwards", we have to start at the left and carry to the right. To add 7 to 3+9.10+9.10^2+..., we add the 7 to the 3, getting 0 carry 1. We then add the 1 to the 9, getting 0 carry 1, etc.)
Also, as we have seen, the p-adic integers seem to contain the reciprocals of some numbers.
(Multiplication in Zp is also done the same way as in Z. For example, to calculate 2 * (3 + 2.5 + 2.5^2 + ...), you multiply each coefficient in the second term by 2, and do any necessary carries. You should be able to see that the answer is 1, showing that the second term is the reciprocal of 2 in Z5.)

The p-adic rationals, Qp

It turns out that, so long as p is prime, Zp contains reciprocals for all numbers not divisible by p. However, it doesn't contain reciprocals of numbers divisible by p. To get a field, we need to add these. Hence, a general element of Qp looks like an element of Zp, multiplied by a (possibly negative) power of p. For example
toQp 5 (1/50) returns Qp 5^-2 [3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

(Mathematically, the p-adic rationals Qp can be constructed in more than one way - either as the p-adic completion of Q, or as the field of fractions of Zp.)

What else?

There's plenty more to say about the p-adics, far more than there is space for here. So, just a few tasters:

Hensel's lemma shows us how to use Newton's method to find solutions to polynomials in Qp. It's very fast - we double the number of digits at each step. For example, we can find square roots:
solvePolyQp 5 (x^2 - 11) returns [Qp 5^0 [1,1,2,0,0,2,0,3,3,2,0,1,4,3,2,3],Qp 5^0 [4,3,2,4,4,2,4,1,1,2,4,3,0,1,2,1]], which are the 5-adic square roots of 11.
solvePolyQp 5 (x^2 + 1) returns the two 5-adic square roots of -1:
[Qp 5^0 [2,1,2,1,3,4,2,3,0,3,2,2,0,4,1,3],Qp 5^0 [3,3,2,3,1,0,2,1,4,1,2,2,4,0,3,1]]
solvePolyQp 5 (x^2 - 2) returns [], because 2 does not have square roots among the 5-adic integers.
So we see that Qp is not algebraically closed. The books show how Qp can be extended to a Cauchy-complete, algebraically closed field, Cp. However, I haven't yet figured out how to represent and manipulate Cp in code.

The usual power series for log(1+x) and exp(x) can also be evaluated over Qp. They have smaller radii of convergence than over the reals. However, in a similar way to analytic continuation in the complex numbers, they can be continued to most of Cp. There is a unique continuation of the logarithm, called the Iwasawa logarithm. However, when we continue the exponential, we have to make some arbitrary choices - so there are many possible continuations, no one of which can be singled out as canonical.
Apparently, log and exp are isometries of Qp - they preserve distance. I haven't figured out what the significance of this is.
(These functions are implemented in the Haskell code as logQp, expQp, and iwasawaLog.)