«
»

Introduction to p-adic integers

By ellipticcurves

I feel like taking a break from elliptic curves and talking about something completely different. For motivation, let’s take a look at solutions of the equation x^2 + x + 3 \equiv 0 \pmod{5^r} for different values of r. For r = 1, we have two solutions: 1, 3 \pmod{5}. For r=2, still two solutions: 8, 16 \pmod{25}. For r=3 we get 33, 91 \pmod{125}. And so on, and so forth.

Notice something interesting. Reduce 91 modulo 25, and you get 16. Reduce 16 modulo 5, and you get 1. Similarly, reduce 33 modulo 25 to get 8, which reduces to 3 modulo 5. It seems like a solution modulo 5 begets a solution modulo 25, which then yields a solution modulo 125, etc. No surprise there, since all we are doing is reducing the equation x^2 + x + 3 \equiv 0 \pmod{5^r} modulo 5^{r-1}.

The question is this. Can we go in the opposite direction and keep this string of solutions going ad infimum? Given a solution modulo 125, can we find one modulo 625?

To make things more general, let us denote polynomial x^2+x+3 by f(x) and 5 by p. Futher, we will always assume that p is prime. We know that there exists a solution a_r \bmod p^r to equation f(a_r) \equiv 0 \pmod{p^r}. Let us for a second suppose that there exists a number a_{r+1} \bmod{p^{r+1}} such that f(a_{r+1}) \equiv 0 \pmod{p^{r+1}} and a_r \equiv a_{r+1} \bmod{ p^r}. Then a_{r+1} \equiv a_r + b_r p^r \bmod{p^{r+1}} for some b_r. Plug this equality into the given equation to get

f(a_r + b_r p^r) \equiv 0 \pmod{p^{r+1}}.

Since f(x) is a polynomial, we can multiply things out, reduce modulo p^{r+1}, where possible, to obtain

f(a_r) + f'(a_r) p^r b_r \equiv 0 \pmod{p^{r+1}}.

(Do this for x^2+x+3 to see that this is precisely what you get when the dust settles.) Move things around, to get

f'(a_r) p^r b_r \equiv -f(a_r) \pmod{p^{r+1}}.

If f'(a_r) is not zero modulo p, then it is also invertible modulo p^{r+1}, and we can divide both sides of this congruence by it to get

b_r p^r \equiv -f(a_r)/f'(a_r) \pmod{p^{r+1}}.

Finally, add a_r to both sides, and remember the definition of a_{r+1} to see that

a_{r+1} \equiv a_r - f(a_r)/f'(a_r) \pmod{p^{r+1}}.

This formula looks precisely like Newton’s Method in Calculus.

One can also quickly check that if c_r is another integer satisfying the defining conditions of b_r, then c_r \equiv b_r \pmod{p}. Note that the only requirement for us to be able to build this chain of solutions is that f'(a_r) \not\equiv 0 \pmod{p}. But a_r \equiv a_1 \pmod{p}. Hence the sole condition for using Newton’s Method to build a chain of solutions modulo p^r for r=1,2,\ldots starting with a_1 is that a_1 be a simple root of f(x) modulo p.

So, we are now dealing with sequences of integer numbers

(a_1, a_2, a_3, \ldots)

such that

a_r \equiv a_{r+1} \pmod{p^r}.

So far as we only care about the congruence class of each a_r modulo p^r, we identify two sequences (a_1, a_2, a_3, \ldots) and (a'_1, a'_2, a'_3, \ldots) if a_r \equiv a'_r \pmod{p^r} for all r=1, 2, \ldots. Check for yourself that this identification is an equivalence relation. The equivalence classes are called the p-adic integers.

Alternative and much more suggestive notation is also available. If we let b_0 = a_1, then we can write a p-adic integer as a formal infinite sum

b_0 + b_1 p + b_2 p^2 + \ldots.

The a_r from the previous paragraph are equal to truncations (reductions modulo p^r) of this sum. To make our lives easier, we choose b_r from the set 0, \ldots, p-1 of representatives of congruence classes modulo p.

The set of p-adic integers contains the set of rational integers \mathbb Z via the map

a \mapsto (a, a, a, \ldots).

In other words, the “usual” integers are represented by constant sequences/finite series.

Going back to our original equation, we find that it has two solutions in {\mathbb Z}_p:

(1, 16, 91, \ldots) = 1 +3\cdot 5 + 3\cdot 5^2 + \cdots

and

(3, 8, 33,\ldots) = 3 + 1\cdot 5 + 1 \cdot 5^2 + \cdots.

This entry was posted on December 25, 2008 at 11:24 pm and is filed under p-adic numbers. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply