# Can one show a beginning student how to use the $p$-adics to solve a problem?

I recently had a discussion about how to teach $p$-adic numbers to high school students. One person mentioned that they found it difficult to get used to $p$-adics because no one told them why the $p$-adics are useful.

As a graduate student in algebraic number theory, this question is easy to answer. But I'm wondering if there's a way to answer this question to someone who only knows very basic things about number theory and the $p$-adics. I'm thinking of someone who has learned over the course of a few days what the $p$-adic numbers are, what they look like, etc, but doesn't know much more.

I'm specifically wondering if there's any elementary problem that one can solve using $p$-adic numbers. It's okay if the answer is no, and that it takes time to truly motivate them (other than more abstract motivation).

• See also Chapter 3 of Titu Andreescu, Gabriel Dospinescu, Straight from the Book, XYZ Press 2012, specifically Addendum 3.B. They build up a lot of the theory of $p$-adic numbers and use it to prove some far-from-trivial binomial congruences. May 6, 2019 at 0:00
• Linking this question also. See Lubin's answer (or Hagen von Eitzen's) for a sleek $p$-adic proof of the fact that a polynomial bijection $\Bbb{Q}\to\Bbb{Q}$ has to be linear. Aug 1, 2020 at 4:07

Here is a very concrete question that can be explained by appealing to the $p$-adic continuity of addition and multiplication. We don't even need completions: the problem takes place entirely in the rational numbers and is not a fake problem in any sense.

We can form binomial coefficients $\binom{r}{n}$ when $r$ is not necessarily an integer, and this is important because they occur in the coefficients of the power series for $(1+x)^r$ in calculus. Their formula, for $n \geq 1$, is $$\binom{r}{n} = \frac{r(r-1)\cdots(r-n+1)}{n!}.$$ If you look at the expansion for $\sqrt{1+x}$ and for $\sqrt[3]{1+x}$, corresponding to $r = 1/2$ and $r = 1/3$, the series start off as $$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 + \cdots$$ and $$1 + \frac{1}{3}x - \frac{1}{9}x^2 + \frac{5}{81}x^3 - \frac{10}{243}x^4 + \frac{22}{729}x^5 + \cdots$$ The surprise is that the denominators are entirely powers of 2 in the first case and 3 in the second case. Think about that: $\binom{1/3}{5}$ involves division by $5!$, but the 2 and 5 factors cancel out. As a more extreme example, $\binom{-3/22}{7} = -\frac{1071892575}{39909726208}$ and $39909726208 = 2^{11}11^7$. Even though the definition of $\binom{-3/22}{7}$ involves division by $7!$, the primes that survive in the denominator seem to have nothing to do with $7!$ and everything to do with the denominator of $-3/22$.

Claim: For $n \geq 1$ and nonzero rational $r$, if a prime $p$ is in the denominator of $\binom{r}{n}$ then $p$ is in the denominator of $r$.

Proof: We show the contrapositive. If $p$ is not in the denominator of $r$ then $|r|_p \leq 1$, so the denominator of $r$ is invertible modulo any power of $p$, and therefore $r$ is a $p$-adic limit of positive integers, say $r = \lim_{k \rightarrow \infty} a_k$ with $a_k \in {\mathbf Z}^+$. That is a $p$-adic limit. By $p$-adic continuity of addition and multiplication (and division), we get $\binom{r}{n} = \lim_{k \rightarrow \infty} \binom{a_k}{n}$, another $p$-adic limit. By combinatorics we know $\binom{a_k}{n}$ is a positive integer, so $|\binom{a_k}{n}|_p \leq 1$. The $p$-adic absolute value on ${\mathbf Q}$ is $p$-adically continuous, so $|\binom{r}{n}|_p = \lim_{k \rightarrow \infty} |\binom{a_k}{n}|_p \leq 1$. Thus $p$ is not in the denominator of $\binom{r}{n}$. QED

The special case $r = 1/2$ can be explained in terms of Catalan numbers: $\binom{1/2}{n} = (-1)^{n-1}C_{n-1}/2^{2n-1}$, where $C_{n-1}$ is the $(n-1)$th Catalan number (a positive integer). Therefore the denominator of $\binom{1/2}{n}$ is a power of 2. For the general case, I know of no argument that explains why primes in the denominator of $\binom{r}{n}$ must be primes in the denominator of $r$ in such a clean way as this $p$-adic method.

The converse of the claim is also true: for $n \geq 1$ and nonzero rational $r$, if a prime $p$ is in the denominator of $r$ then $p$ is in the denominator of $\binom{r}{n}$. That is, if $|r|_p > 1$ then $|\binom{r}{n}|_p > 1$. More precisely, if $|r|_p > 1$ then $|\binom{r}{n}|_p \geq |r|_p^n$, so in fact $|\binom{r}{n}|_p \rightarrow \infty$ as $n \rightarrow \infty$. Let's leave that as an exercise. (The data for the coefficients of $\sqrt{1+x}$ and $\sqrt[3]{1+x}$ suggest that perhaps the sequence $|\binom{r}{n}|_p$ is monotonically increasing if $|r|_p > 1$, and that too can be proved in general by looking at the $p$-adic absolute value of the ratio $\binom{r}{n+1}/\binom{r}{n}$.) In particular, for $n \geq 1$ the denominator of $\binom{1/2}{n}$ is a power of $2$ other than $1$.

My personal elementary favorites are:

• Prove that $$\frac11+\frac12+\frac13+\cdots+\frac1n$$ is not an integer, if $n>1$.
• And the variant of proving that $$\frac11+\frac13+\frac15+\cdots+\frac1{2n+1}$$ is not an integer, if $n\ge1$.

Both are resolved by using the non-archimedean $p$-adic triangle inequality for a suitable choice of $p$.

• This also leads to a natural open problem: show $|1 + 1/2 + \cdots + 1/n|_p \rightarrow \infty$ as $n \rightarrow \infty$. That is, the harmonic sums should diverge in every $\mathbf Q_p$, just like they do in $\mathbf R$.
– KCd
May 20, 2014 at 21:22
• @KCd That's open? Astonishing.
– user98602
May 20, 2014 at 21:48
• It's not open for some specific $p$, but it is for $p$ in general. For instance, it is known to be true for primes $p \leq 11$. See math.uconn.edu/~kconrad/blurbs/ugradnumthy/padicharmonicsum.pdf and the references there.
– KCd
May 20, 2014 at 21:56

An example for Hasse-Minkowski might be worth studying it, i.e., the binary quadratic form $5x^2 + 7y^2 − 13z^2$ has a non-trivial rational root since it has a $p$-adic one for every prime, and obviously also a real root.

Another example is the $3$-square theorem of Gauss: A positive integer $n$ is the sum of three squares if and only if $-n$ is not a square in $\mathbb{Q}_2$, the field of $2$-adic integers.

• How does it have a p-adic root for all primes $p$? (I don't know much about p-adic numbers) May 27, 2014 at 17:46
• @MayankPandey, the non-trivial rational solution is a $p$-adic solution for all $p$: $(3,1,2)$. The point, though, is that using p-adic properties (Hilbert symbols) you can show there is a $p$-adic solution for each $p$ with those solutions being priori unrelated to each other.
– KCd
Oct 19, 2016 at 12:05

A nice application is a proof of Gauss's lemma: if $f$ is a monic polynomial with integer coefficients which factors as $gh$ in $\mathbf Q[x]$, with both $g, h$ monic, then $g$ and $h$ also have integer coefficients. This involves defining the $p$-adic absolute value on polynomials as $\left|\sum a_i x^i\right|_p := \max |a_i|_p$, and then showing that $|gh|_p = |g|_p|h|_p$. Since $g$ and $h$ are monic we have $|g|_p \geq 1$ and $|h|_p \geq 1$ because $|1|_p = 1$. Since $|f|_p = 1$, we must also have $|g|_p|h|_p = 1$, so therefore $|g|_p = 1$ and $|h|_p = 1$ - that is, the coefficients of $g$ and $h$ must be $p$-integral. Since this is true for all $p$, the coefficients of $g$ and $h$ are integers. This is much cleaner than the proof using gcds/lcms of the numerators or denominators of the coefficients, and shorter than proofs that require the development of algebraic integers.

The usual proof of Gauss's lemma relies on the product of two primitive polynomials in ${\mathbf Z}[x]$ being primitive, where a polynomial $f(x)$ in $\mathbf Z[x]$ is called primitive when its coefficients have no common prime factor, or equivalently when $|f|_p = 1$ for all primes $p$. If $f$ and $g$ are primitive in $\mathbf Z[x]$ (not the same $f$ and $g$ as above!), we have $|f|_p = 1$ and $|g|_p = 1$ for all $p$, so $|fg|_p = |f|_p|g|_p = 1$ for all $p$, and therefore $fg$ is primitive!

This is also quite a striking application of $p$-adic numbers, but it's not constructive as it involves extending the $2$-adic absolute value to the real numbers. Use at your own risk!

I'm not sure to what extent this addresses your question, but hopefully you find something interesting here. This actually was the way I first got introduced to the p-adics, so it was a good example for one person at least...

This is the last problem from the 2001 Bay Area Mathematical Olympiad:

For each positive integer $n$, let $a_n$ be the number of permutations $\tau$ of $\{1,2,\ldots,n\}$ such that $\tau(\tau(\tau(x)))=x$ for $x = 1,2,\ldots,n$. The first few values are $a_1 = 1,a_2 = 1,a_3 = 3,a_4 = 9$. Prove that $3^{334}$ divides $a_{2001}$.

This can be solved with elementary methods, but the result itself is not tight—in fact, $3^{445}$ divides $a_{2001}$. In general, $\nu_3 (a_n) \sim \frac{2}{9}n$.

As far as I know, this last fact requires working over the $3$-adics . The point is that $\sum_k a_k \frac{x^k}{k!}$, the exponential generating function for $a_n$, exactly equals $e^{x+\frac{1}{3}x^3}$, and finding an asymptotic expression $\nu_3 (a_n) \sim c n$ is equivalent to finding the radius of convergence, related by $R=3^{c-\frac{1}{2}}$ (here we use the fact that $\nu_3(k!)\sim \frac{1}{2}k$).

This is not necessarily the cleanest "application" of the p-adics, but I think it's an interesting place to start asking questions. For example, why does the power series for $e^x$ have 3-adic radius of convergence $3^{-\frac{1}{2}}$, but for $e^{x+\frac{1}{3}x^3}$ the radius increases to $3^{-\frac{1}{6}}$? For me, this yielded some intuition about the Artin-Hasse exponential $e^{x+\frac{1}{3}x^3+\frac{1}{3^2}x^{3^2}+\ldots}$, whose power series has radius of convergence 1.

• So $a_n$ is the number of solutions of $g^3 = (1)$ in $S_n$. More generally, if you pick a prime $p$ and let $a_{n,p}$ be the number of solutions of $g^p = (1)$ in $S_n$ then $\sum_{n \geq 0} (a_{n,p}/n!)x^n = e^{x+x^p/p}$. If you let $a_{n,G}$ be the number of homomorphisms $G \rightarrow S_n$, and $a_{0,G} = 1$, then $\sum_{n \geq 0} (a_{n,G}/n!)x^n = \exp(\sum_{H \subset G} x^{[G:H]}/[G:H])$. Here $G$ is finite. If $G$ is profinite and topologically finitely generated, and count continuous homomorphisms to the $S_n$'s then the formula still works, with $H$'s being open subgroups of $G$.
– KCd
May 16, 2014 at 23:06

While this may not be novel with respect to the $p$-adic numbers, one can show that $x^2-2=0$ has no solution in $\mathbb{Q}_5$, and therefore it follows that $\sqrt{2}$ is not rational. There are of course many other examples of this nature, perhaps one can find some more interesting ones.