# Elementary results with p-adic numbers

I'm giving a talk for the seminar of the PhD students of my math departement. I actually work on Berkovich spaces and arithmetic geometry but, of course, I cannot really talk about that to an audience that includes probabilists, computer scientists and so on.

I'd rather like to do an introduction to $p$-adic numbers and $p$-adic analysis. I think these kind of things come up to be really cool when you work on it even just for a short time, but I have the ambitious aim to show them something nice and elementary whose statement will be understood by everyone (of course the proof may also be really hard, but there I could give them just its general idea).

In other words the question is: if I had prepared something about Galois theory I would have finished with the application to resolubility of polynomial or compass and straightedge constructions; if it had been something about modular forms, it would have been for sure Fermat's last theorem; with 3-surfaces it would have been Poincaré conjecture and so on. What if it's about p-adic numbers or p-adic analysis?

I thought about results on valuations of roots of polynomials, but it seems to me already too complicated (par ailleurs since I'm introducing valuations at the beginning of the talk, it won't turn out to be an application to something they already knew).

-
Local-to-global results, for instance for quadratic and cubic forms (Hasse principle). See en.wikipedia.org/wiki/Hasse_principle and Chapter 1 of Serre's book "A course in arithmetic". – Francesco Polizzi Nov 19 '11 at 14:22
One motivation for building the p-adic integers is to mimic the taylor series expansions for rational functions in the complex numbers. This could be a lecture by itself - start with some very elementary property of rational functions, and then write down the 'corresponding' property for the expansion of a rational number base p. – Robert Garbary Nov 19 '11 at 14:28
If you have computer scientists in the audience, don't forget to mention the connection between two's complement arithmetic and the 2-adics. Practical application: using Newton-Raphson to compute multiplicative inverses modulo $2^n$, useful for fast exact integer division. – Dan Piponi Nov 19 '11 at 15:48
One can prove that there is a primitive element modulo $p^n$, i.e. $(\mathbb{Z}/p^n\mathbb{Z})^{\times}$ is cyclic, for all $n\geq 1$ by using the case $n=1$ and the $p$-adic logarithm. Also, this explains that the discrete logarithm problem is not more difficult for $p^n$ than it is for $p$. – Chris Wuthrich Nov 19 '11 at 18:43
There's a theorem by Monsky (see jstor.org/stable/2317329) that a square cannot be divided into an odd number of triangles of equal areas. This is a purely geometrical statement, but the proof basically uses 2-adic numbers! – Laurent Berger Nov 19 '11 at 19:54

Introduce ${\mathbf Z}_p$ as "formal" infinite base $p$ expansions where you add and multiply by carrying (any other description will probably take too long and not be concrete). Show them the series for $-1$ in ${\mathbf Z}_3$ is $2 + 2\cdot 3 + 2 \cdot 3^2 + 2 \cdot 3^3 + \cdots$ by adding 1 to that, carrying, and killing off a new term at each step so the sum is 0. Then emphasize the idea that in ${\mathbf Z}_p$ the number $p$ is small and redo the previous computation with geometric series: $2/(1 - 3) = 2/(-2) = -1$. Show ${\mathbf Z}_3$ contains a square root of 7: $1 + 3 + 3^2 + 2 \cdot 3^4 + 2 \cdot 3^5 + \cdots$.

(To explain why $p$ being prime is important, say the $p$-adic integers form an integral domain, and for a contrast you could define $Z_{10}$ in a similar way and say there is a number $x$ in ${Z}_{10}$ besides 0 and 1 satisfying $x^2 = x$: $x = 5 + 2\cdot 10 + 6\cdot 10^2 + 9\cdot 10^4 + 8\cdot 10^5 + \cdots$. Compute the first few digits of $x^2$ to check this works. This is related to the elementary school question of finding integers whose square ends in themselves: $5^2$ ends in 5, $25^2$ ends in 25, $625^2$ ends in 625, and so on. The 10-adic solution of $x^2 = x$ which I wrote the initial expansion of above packages all of this information into one number.)

You could introduce a topology on ${\mathbf Z}_p$ where numbers are close if a long string of initial digits are the same and make a metric from this too. Then indicate how this makes ${\mathbf Z}_p$ compact by a sequential argument, in the same spirit in which $[0,1]$ is compact by an argument with decimal expansions. A key new feature here, which those with experience only in real and complex analysis haven't seen before, is that ${\mathbf Z}_p$ is a compact ring. In ordinary geometry there are plenty of compact groups, but no compact rings.

A nice application of this compactness is the finiteness of integral solutions to certain equations. For example, $x^2 - 7y^2 = 1$ has an infinite number of integral solutions, but $x^3 - 7y^3 = 1$ has just two integral solutions: (1,0) and (2,1). One way to prove this finiteness is to use $3$-adic power series. By algebraic methods one can show that if integers $x$ and $y$ satisfy $x^3 - 7y^3 = 1$ then $x - y\sqrt[3]{7} = (2-\sqrt[3]{7})^n$ for some integer $n$; the solutions $(x,y) = (1,0)$ and $(2,1)$ correspond to $n = 0$ and $n = 1$, respectively. When you expand $(2-\sqrt[3]{7})^n$ (say, by the binomial theorem when $n > 0$) you get a formula $a_n + b_n\sqrt[3]{7} + c_n\sqrt[3]{49}$ with integer coefficients $a_n, b_n, c_n$ and we want $c_n = 0$. That is a very strong constraint, since normally you don't expect $c_n = 0$. There is an exponential formula for $c_n$ in terms of $n$: $$c_n = \frac{1}{21}\left(\sqrt[3]{7}(2 - \sqrt[3]{7})^n + \omega\sqrt[3]{7}(2 - \omega\sqrt[3]{7})^n + \omega^2\sqrt[3]{7}(2 - \omega^2\sqrt[3]{7})^n\right),$$ where $\omega$ is a cube root of unity. In the same way $a^x$ can be expanded as a real power series in $x$ when $a > 0$, the formula for $c_n$ above can be expanded into a $3$-adically convergent power series in $n$ by interpreting $\omega$ and $\sqrt[3]{7}$ to be a cube root of unity and a cube root of 7 in the 3-adics. (Strictly speaking you need to pass to a finite extension of the 3-adics to pick up a cube root of unity, but let's gloss over that point.) Asking for $c_n$ to be 0 is then asking for $n$ to be an integral root of a 3-adic power series. Just as a nonzero analytic function on a closed (hence compact) disc in ${\mathbf C}$ has finitely many roots in the disc, a 3-adic power series that converges on ${\mathbf Z}_3$ has finitely many roots in ${\mathbf Z}_3$. Since ${\mathbf Z}$ is inside of ${\mathbf Z}_3$ this implies in particular that there are finitely many roots in ${\mathbf Z}$. To make this result effective (i.e., to know $n=0$ and $n=1$ are the only 3-adic roots of that power series), you need techniques to bound the number of $3$-adic roots of a $3$-adic power series, and that goes beyond the scope of your talk. :) Details are written, for instance, in section 6.4.7 of Henri Cohen's "Number Theory I: Tools and Diophantine Equations". This technique of proving effective finiteness theorems for integral solutions of Diophantine equations by $p$-adic methods goes back to work of Strassman and Skolem and later developments in this direction are due to Chabauty and Coleman. However, even without an effective bound it's striking to see that the finiteness of integral solutions to an equation can be explained by an argument inspired by finiteness of zeros of a holomorphic function in a compact set, by sticking the integers into a compact domain on which a (3-adic) power series converges.

Here is a cute application of $2$-adic continuity of polynomials (as a contrast to continuity of polynomials in the "usual" topology your audience will know). If we write out $\sqrt{1+x}$ as a power series it is $$\sqrt{1+x} = \sum_{n \geq 0} \binom{1/2}{n}x^n = 1 + \frac{1}{2}x - \frac{1}{8}x^2 + \frac{1}{16}x^3 - \frac{5}{128}x^4 + \frac{7}{256}x^5 - \frac{21}{1024}x^6 + \cdots$$ and a striking feature is that the coefficients all have denominators that are powers of 2. It's not a surprise there is some power of 2 in the denominator considering a formula for the coefficient of $x^n$ is $$\binom{1/2}{n} = \frac{(1/2)(1/2-1)(1/2-2)\cdots(1/2-n+1)}{n!},$$ but why are there are no other primes in the denominator when you simplify the right side? One answer, which doesn't use anything $p$-adic, is to grind out the algebra and check that $$\binom{1/2}{n} = \frac{(-1)^{n-1}}{2^{2n-1}}\left(\binom{2n-2}{n-1} - \binom{2n-2}{n}\right).$$ The binomial coefficients on the right are integers so the denominator is a power of 2. (That difference of binomial coefficients has a combinatorial interpretation as the $(n-1)$-th Catalan number.) Here is a slicker explanation of why the denominator is a power of 2: instead of directly seeing the power of 2 in the denominator of the rational number $\binom{1/2}{n}$, we will instead show for any prime $p$ other than 2 that $\binom{1/2}{n}$ is a $p$-adic integer, so it has no $p$ in its denominator as a reduced fraction. For odd $p$ we have the $p$-adic limit formula $\frac{1}{2} = \lim_{k \rightarrow \infty} \frac{p^k+1}{2}$, and the terms in that limit sequence are integers. The polynomial function $\binom{X}{n} \in {\mathbf Q}[X]$ is continuous in the $p$-adic topology, just as polynomials in ${\mathbf Q}[X]$ are continuous in the "usual" topology (in the reals), so by $p$-adic continuity $$\binom{1/2}{n} = \lim_{k \rightarrow \infty} \binom{(p^k+1)/2}{n}.$$ Every binomial coefficient on the right is a positive integer for large $k$, so $\binom{1/2}{n}$ is a $p$-adic limit of integers and therefore is a $p$-adic integer. This means $\binom{1/2}{n}$ has no $p$ in its denominator. This holds for all odd $p$, so the only prime in the denominator of $\binom{1/2}{n}$ is 2.

The same basic idea shows for any nonzero rational number $r$ that the primes in the denominator of $\binom{r}{n}$ are limited to the primes in the denominator of $r$. For instance, the only primes in the denominator of $\binom{14/75}{n}$ are 3 and 5 because, with experience, one can see with $p$-adic limits that this fraction is $p$-adically integral for any $p$ other than 3 or 5. I doubt you're going to find a proof of that fact by some "explicit formula" method like the first proof I indicated for $\binom{1/2}{n}$ only having 2's in its denominator.

-

Here is a beautiful and essentially elementary result using the $p$-adics: the Skolem-Mahler-Lech theorem.

Theorem. (Skolem-Mahler-Lech) Let $(a_i)$ be a sequence defined by an integer linear recurrence. Then the set of $i$ such that $a_i=0$ is the union of a finite set with finitely many arithmetic progressions.

A quick proof may be found on Terry Tao's blog, here. Essentially, the $p$-adic step of the proof works by defining a $p$-adic analytic function with infinitely many zeros, and then concluding that this function is identically zero--by the definition of this function, this gives some congruence information about the structure of the zero set of the linear recurrence, as desired. The proof is quite elementary and beautiful, and I think accessible to people seeing the $p$-adics for the first time.

-
This theorem of Skolem's is closely related to the one I wrote about at the end of my answer (using $p$-adic power series and compactness to prove a finiteness theorem), so it would be good to mention both of them together. It would be useful to provide a concrete example of this theorem where one can write down the arithmetic progressions. – KConrad Nov 19 '11 at 17:50
There is an exposition of this material in my paper with Alf van der Poorten, Some problems concerning recurrence sequences, Amer. Math. Monthly 102 (1995) 698-705. – Gerry Myerson Nov 19 '11 at 22:53

Here are three more elementary results whose most natural proof involves $p$-adic ideas. All three can be found in Cassels' book on Local Fields (edit mentioned by Laurent Berger in a comment).

The first one is Witt's proof of the theorem of Clausen and von Staudt in Chapter 1. It requires nothing more than the definition of the $p$-adic valuations; the idea is that $a\in{\bf Q}$ is in ${\bf Z}$ if $a\in{\bf Z}_p$ for every prime $p$.

The second one says that the order of every finite subgroup $G\subset{\mathrm GL}_n({\mathbf Q})$ divides $$\prod_l l^{\beta(l)}$$ where $l$ runs over the primes and $$\beta(l)=\lfloor n/(l-1)\rfloor+\lfloor n/l(l-1)\rfloor+\lfloor n/l^2(l-1)\rfloor+\cdots$$ for $l\neq2$ and $\beta(2)=n+2\lfloor n/2\rfloor+\lfloor n/2^2\rfloor+\lfloor n/2^3\rfloor+\cdots$. See Theorem 2.1 in Chapter 4.

The third one is a theorem of Selberg which says that every finitely generated subgroup $G\subset{\mathrm GL}_n(k)$, where $k$ is a field of characteristic $0$, contains a normal torsionfree subgroup of finite index. See Theorem 4.1 in Chapter 5.

Note finally that the (Skolem)-Mahler-Lech theorem is Theorem 5.1 in the same chapter.

Addendum. Since I had already TeXed Witt's proof for my Notes, it is easy to reproduce it here :

Theorem (von Staudt--Clausen, 1840)
Let $k>0$ be an even integer, and let $l$ run through the primes. Then the number $$(1)\quad\quad\quad W_k=B_k+\sum_{l-1|k}{1\over l}$$ is always an integer. For example, $\displaystyle W_{12}=B_{12}+{1\over 2}+{1\over3}+{1\over5}+{1\over7}+{1\over 13}=1$.

[The British analyst Hardy says in his Twelve lectures (p. 11) that this theorem was rediscovered by Ramanujan at a time of his life when he had hardly formed any definite concept of proof''.]

Proof (Witt) : The idea is to show that $W_k$ is a $p$-adic integer for every prime $p$. More precisely, we show that $B_k+p^{-1}$ (resp. $B_k$) is a $p$-adic integer if $p-1|k$ (resp. if not).

For an integer $n>0$, let $S_k(n)=0^k+1^k+2^k+\cdots+(n-1)^k$. Comparing the coefficients on the two sides of $$1+e^T+e^{2T}+\cdots+e^{(n-1)T}={e^{nT}-1\over T}{T\over e^T-1},$$ we get $\displaystyle S_k(n) =\sum_{m\in[0,k]}{k\choose m}{B_m\over k+1-m}n^{k+1-m}$. To recover $B_k$ from the $S_k(n)$, it is tempting to take the limit $\displaystyle\lim_{n\to0}S_k(n)/n$, which doesn't make sense in the archimedean world. If, however, we make $n$ run through the powers $p^s$ of a fixed prime $p$, then, $p$-adically, $p^s\to0$ as $s\to+\infty$, and $$(2)\quad\quad\quad\lim_{s\to+\infty}S_k(p^s)/p^s=B_k.$$ Let us compare $S_k(p^{s+1})/p^{s+1}$ with $S_k(p^s)/p^s$. Every $j\in[0,p^{s+1}[$ can be uniquely written as $j=up^s+v$, where $u\in[0,p[$ and $v\in[0,p^s[$. Now, \eqalign{ S_k(p^{s+1}) &=\sum_{j\in[0,p^{s+1}[}j^k=\sum_{u\in[0,p[}\sum_{v\in[0,p^s[}(up^s+v)^k\cr % &\equiv p\left(\sum_{v\in[0,p^s[}v^k\right) % +kp^s\left(\sum_{u\in[0,p[}u\sum_{v\in[0,p^s[}v^{k-1}\right) % \pmod{p^{2s}}\cr &\equiv p\left(\sum_v v^k\right) +kp^s\left(\sum_u u\sum_v v^{k-1}\right)\pmod{p^{2s}}\cr } by the binomial theorem. As $\sum_{v}v^k=S_k(p^s)$ and $2\sum_uu=p(p-1)\equiv0\pmod p$, we get $$S_k(p^{s+1})\equiv pS_k(p^s)\pmod{p^{s+1}},$$ where, for $p=2$, the fact that $k$ is even has been used. Dividing throughout by $p^{s+1}$, this can be expressed by saying that $${S_k(p^{s+1})\over p^{s+1}}-{S_k(p^s)\over p^s}\in{\mathbf Z}_{(p)}$$ is a $p$-adic integer, and therefore $${S_k(p^r)\over p^r}-{S_k(p^s)\over p^s}\in Z_{(p)}$$ for any two integers $r>0$, $s>0$, since ${\mathbf Z}_{(p)}$ is a subring of $\mathbf Q$. Fixing $s=1$ and letting $r\to+\infty$, we see that $B_k-S_k(p)/p\in{\mathbf Z}_{(p)}$, in view of $(2)$. We need a

Lemma. $S_k(p)=\sum_{j\in[1,p[}j^k$ is $\equiv-1\pmod p$ if $p-1|k$ and $\equiv0\pmod p$ otherwise.

This is clear if $p-1|k$. Suppose not, and let $g$ be a generator of $({\mathbf Z}/p{\mathbf Z})^\times$. We have $g^k-1\not\equiv0$, whereas $$(g^k-1)\left(\sum_{j\in[1,p[}j^k\right) \equiv (g^k-1)\left(\sum_{t\in[0,p-1[}g^{tk}\right) \equiv g^{(p-1)k}-1\equiv0.$$ It follows that $B_k+p^{-1}\in{\mathbf Z}_{(p)}$ if $p-1|k$ and $B_k\in{\mathbf Z}_{(p)}$ otherwise. In either case, the number $W_k$ (1), which can be written as $$W_k=\cases{ (B_k+p^{-1})+\sum_{l\neq p}l^{-1}&\hbox{if }p-1|k\cr (B_k)+\sum_l l^{-1}&\hbox{otherwise},\cr }$$ (where $l$ runs through the primes for which $l-1|k$) turns out to be a $p$-adic integer for every prime $p$. Hence $W_k\in{\mathbf Z}$, as claimed.

-
In the same spirit, if not the same proof, one can show $p$-adically that, after restriction to its elements of finite order, $\mathop{\rm SL}_n(\mathbf Z)$ injects in $\mathop{\rm SL}_n(\mathbf Z/p\mathbf Z)$ (for $p>3$). This can be understood as the fact that $p$-adic matrices congruent to the identity modulo $p$ correspond to the tangent space of the $p$-adic Lie group $\mathop{\rm SL}_n(\mathbf Z_p)$. Consideration of the $p$-adic exponential map implies the result. – ACL Nov 21 '11 at 19:01

For a mind bending example, there are sequences of rationals that converge both p-adically and in the real sense to rational numbers, but not the same rational number.

-
All the suggestions have been good, but this simple fact, a commonplace to us old hands, is just the sort of thing that can raise an outsider's eyebrows. – Lubin Nov 19 '11 at 23:31
If you're not careful with this, you can give a very short proof that $\pi$ is irrational. Say it equals $a/b$, write $\sin(a/b) = 0$ and expand the series : it converges $p$-adically if $p$ divides $a$, and you get a contradiction ... except that it does not necessarily converge to $\sin(\pi)=0$! – Laurent Berger Nov 20 '11 at 8:23
One can write down an example of this very easily. Fixing a prime number $p$, as $n \rightarrow \infty$ the sequence $p^n/(p^n+1)$ converges to 1 in the reals and to 0 in the $p$-adics while $1/(p^n+1)$ converges to 0 in the reals and to 1 in the $p$-adics. So for your favorite rationals (or just integers) $r$ and $s$, $rp^n/(p^n+1)+s/(p^n+1)$ converges to $r$ in the reals and to $s$ in the $p$-adics. – KConrad Nov 22 '11 at 3:09
Laurent: the series $\sin(a/b)$ converges $p$-adically if $p|a$ when $p$ is odd, but the 2-adic disc of convergence of $\sin(x)$ in ${\mathbf Q}_2$ is $4{\mathbf Z}_2$ rather than $2{\mathbf Z}_2$. So if $\pi$ has an even numerator then one can gets a (fake) contradiction with $p=2$ by running through the argument with $2\pi$ in place of $\pi$. – KConrad Nov 23 '11 at 19:55
My previous comment about needing $2\pi$ instead of $\pi$ when $p=2$ was incorrect. One only has to consider $p=2$ if no odd $p$ appears in the numerator of $\pi$. Then the numerator of $\pi$ is a power of 2. The numerator can't be 2 since $\pi > 3$, so the numerator of $\pi$ would be divisible by 4 and we can use the argument for $p=2$ directly on $\pi$ instead of $2\pi$. – KConrad Nov 24 '11 at 16:39

Chris Wuthrich has mentioned that the structure of the group $({\bf Z}/p^n{\bf Z})^\times$ can be easily determined by $p$-adic methods. These local methods are really indispensable for determining the structure of the group $({\mathfrak o}/{\mathfrak p}^n)^\times$ in general, where ${\mathfrak o}$ is the ring of integers in a number field and ${\mathfrak p}\subset{\mathfrak o}$ is a prime ideal. See Chapter 15 of Hasse's Number Theory.

As a related application, consider Wilson's theorem ($(p-1)!\equiv-1\pmod p$ for a prime number $p$). More generally, Gauss (Disquisitiones, $\S$78) determined the product of all elements of $({\bf Z}/a{\bf Z})^\times$ for every $a>0$. There are now two possibilities, $+1$ and $-1$, and Gauss proves that the product is $-1$ precisely when $a$ is $4$, or $p^m$, or $2p^m$ for some odd prime $p$ and integer $m>0$.

For an ideal ${\mathfrak a}\subset{\mathfrak o}$ in the ring of integers of a number field, what is the product of all elements in $({\mathfrak o}/{\mathfrak a})^\times$ ? There are now four possibilities, and one can say which one occurs when. This turns out to be a result of Laššák Miroslav (2000) but I had a lot of fun a few years ago giving a simple $p$-adic proof in JTNB (or arXiv).

Addendum. Laššák's paper is available online now-a-days.

-

In other words the question is: if I had prepared something about Galois theory I would have finished with the application to resolubility of polynomial or compass and straightedge constructions; if it had been something about modular forms, it would have been for sure Fermat's last theorem; with 3-surfaces it would have been Poincaré conjecture and so on. What if it's about p-adic numbers or p-adic analysis?

These results have very different levels of sophistication. I would propose the Weil conjectures as an application : http://en.wikipedia.org/wiki/Weil_conjectures#Statement_of_the_Weil_conjectures

The first statement (rationality of the Zeta function) was originally proved by Dwork using purely $p$-adic methods. It's a beautiful application of $p$-adic analysis and $p$-adic functional analysis. In addition, it should not be too hard to state the theorem, since it's about counting solutions of polynomials in finite fields.

Finally, you can also say that Kedlaya now has given a purely $p$-adic proof of the complete conjecture (previously proved by Deligne using other methods).

-
And the down-to-Earth application of it is : Given a polynomial $f$ with integer coefficients in several variables. In a finite amount of computations we can decide if $f$ has a root modulo $m$ for all $m>1$ or not. That of course is the quickest way to rule out that $f$ has an integer solution. The same works for systems of polynomial equations. – Chris Wuthrich Nov 20 '11 at 9:20

The suggestion of Maurizio Monge about the Hensel lemma is a good one in my opinion ; as an application, I suggest to study which integers have square roots in the various completions of the rationals, and hence see they are not isomorphic.

Mahler's theorem about continuous functions would probably be pretty nice.

Amice's exposition might be a nice basis, too.

-
-
Dear @Robert L Brown, it would be nice if you could add a short description of the linked content into your answer. Answers consisting solely of links become invalid once the links change or rot. – Ricardo Andrade Apr 2 '14 at 10:29
Yes, a prose description of what the reader can expect or should look for when clicking on those links would be much preferred. Any personal insights you have would be a plus. – Todd Trimble Apr 2 '14 at 13:08

If you don't mind doing something really elementary, you can prove that the ten-adic integers $\mathbb{Z}_{10}$ is not an integral domain and show it is actually $\mathbb{Z}_{2}\oplus\mathbb{Z}_{5}$.

-
It's nice that even a primary-school pupil, maybe armed with a calculator, can verify that $\mathbb{Z}_{10}$ is not an integral domain. Namely, such a child might wonder: Is there a number $x$ such that the last few digits of $x^2$ coincide with those of $x$? $5$ is an obvious first choice, but more digits are possible: $25$ ($25^2 = 625$), $625$ ($625^2=390625$), $90625$ ($90625^2 = 8212890625$), and so on. These approximations actually describe a single $10$-adic number $x$ which satisfies the identity $x^2=x$, or equivalently $x(x-1)=0$. Since $x$ is neither zero nor one, the claim follows. – Ingo Blechschmidt Jan 22 at 15:11

You could mention Fermat's last theorem: Kummer's proof (in the regular case) uses properties of Bernoulli numbers that are close to the existence of the p-adic zeta function, and Wiles's proof uses p-adic numbers in at least 3 ways.

-