Classical number theoretic applications of the $p$-adic numbers

I am sure we can all agree that the $p$-adic numbers are highly fascinating objects in their own right - just as the closely related theory of valuations.

Having independently read up on the $p$-adic numbers for a few weeks now, I have so far only seen one application of them to what I would call classical number theory - namely the proof given in Serre's Cours d'arithmétique that a natural number is expressible as the sum of $\leq 3$ squares if and only if it is not of the form $4^a(8b-1)$ for some $a,b \in \mathbb{N}$.

Since I have a tendency to appreciate the value of the higher theories of mathematics in proportion to their applications to elementary number theory, I immediately found myself wondering if there are any other applications.

So my question to the community is: What are the most delightful applications of the $p$-adic numbers and the theory of valuations to elementary number theory?

Many thanks.

P.s.: I am aware that there are already several posts on the forum about the applications of the $p$-adic numbers, but none that refers to elementary number theory specifically.

Edit: I agree that I have been too vague in what I mean by "elementary number theory", so I will try to be a little more specific: By a classical "elementary" number theoretic proposition, I mean a number theoretic proposition that Fermat might have come up with. Thus, the above proposition about the sum of three squares is an elementary number theoretic proposition, as is e.g. Fermat's Last Theorem and the Twin Prime Conjecture, while e.g. the BSD Conjecture or the Class Number Problem are not.

Edit 2: Thank you for all the answers below - they are all excellent! In case anyone should come up with another one, I should like to say that bonus-points are given for results that have so far only been proven using the theory of $p$-adic numbers, or whose proof using $p$-adic numbers is far more conceptual and insightful than the original / more elementary one.

Solution 1:

One of my favourite classical results using $p$-adic methods in elementary number theory is the theorem of Skolem-Mahler-Lech:

This is a theorem about linear recurrence sequences, which are sequences of integers where each term is a fixed linear combination of $n$ previous ones. So fixing $n$ the sequence $s_i$ is defined by choosing the first $n$ terms $$s_0,\ldots, s_{n-1}\in \mathbf Z$$ and a relation for all $k$ $$s_{k + n} = \sum_{i=0}^{n-1} a_i s_{k+i}$$ for fixed $a_i$.

Some examples are the Fibonacci sequence ($n = 2$,$s_0 = 0, s_1 = 1$, $a_0=a_1= 1$), and simpler things like any eventually periodic sequence, or the sequence $s_k = k$ (here $n=2$, $s_0 = 0, s_1=1$, $a_0 = -1, a_1= 2$). We can make other such sequences easily by noting that that the sum of any two linear recurrence sequences is also a linear recurrence sequence.

An important fact about such sequences are that their generating functions $$f_s = \sum_{k= 0}^\infty s_k x^k$$ are always rational functions of the variable $x$ (one polynomial divided by another), where the numerator defines the initial terms $s_0, \ldots, s_{n-1}$ and the denominator defines the recurrence relation.

Of the examples I mentioned above, the fibonacci sequence grows (exponentially), eventually periodic sequences are bounded, and the sequence $s_k=k$ also grows, just less quickly than fibonacci.

One question that one might then ask is:

What is the set of $k$ for which $s_k = 0$?

from these examples (and others) we might conjecture that this set is periodic, except for finitely many exceptions (after all we can always change finitely many terms of any linear recurrence sequence to make a sequence with the same behaviour eventually but with zeroes wherever we want at the start).

How might one go about proving this? The first step of the proof is to use the rational generating function $f_s$ and write out its partial fraction decomposition over an algebraically closed field (like $\overline {\mathbf Q}$), this will be of the form

$$f_s = \sum_{i=1}^{\ell} \sum_{j = 1}^{r_i} \frac{\alpha_{ij}}{(x - \beta_{i})^j} $$

for some fixed roots $\beta_j$ of the original denominator of $f_s$.

Now using this decomposition we have $$f_s = \sum_{i=1}^{\ell} \sum_{j = 1}^{r_i} \alpha_{ij}{\left(\sum_{n=0}^\infty \beta_i^n x^n\right)^j} $$

what this gives is that $$s_n = \text{some polynomial expression involving terms }\beta^n $$

For example for the fibonacci sequence this recovers Binet's formula $$s_n = \frac{1}{\sqrt 5} \left(\frac{1+ \sqrt 5}2\right)^n-\frac{1}{\sqrt 5} \left(\frac{1- \sqrt 5}2\right)^n.$$ Or for the periodic sequence $0,1,0,1,0,1,\ldots$ this is $$ s_n = 1^ n - (-1)^n$$

So we've written $s_n$ as a sum of exponential-type functions in $n$ with different bases, that we want to describe the zeroes of this function for $n \in \mathbf N$.

Now the magic part: the function $e^x$ is an analytic function, and on a bounded domain analytic functions have only finitely many zeroes (unless they are zero everywhere). This would give us a lot of control over the zeroes of $s_n$ if the naturals were bounded. Which leads to the slightly strange question:

What if the natural numbers were bounded? And the functions $\beta^n$ were still analytic in some way?

Of course using the usual absolute value and metric on $\mathbf Q$ and $\mathbf C$ this is totally false.

But in the $p$-adic numbers this is true! The integers are all bounded ($p$-adically) by norm $\le 1$. So lets treat these functions as $p$-adic functions and control the zero sets in some way.

How does this prove the result? The functions $\beta^n$ are not $p$-adic analytic functions of $n$ on their own, but they are so on small enough $p$-adic disks though, what ends up happening is we get distinction between congruence classes of $n$ mod $p-1$ for some well-chosen $p$ such that in each congruence class there are only finitely many zeroes of $s_n$ or the function $s_n$ is identically zero on that congruence class. This gives us the theorem mentioned above, that the zeroes of $s_n$ are periodic, except for finitely many exceptions.

Solution 2:

You write that there are "no posts" on this forum that refer to using the $p$-adics in an elementary number theory setting. A universal claim can be refuted with a single counterexample, so look at the answers here for some elementary applications of $p$-adics, including one I mention there about determining the primes in the denominators of binomial coefficients $\binom{r}{n}$ for $r \in \mathbf Q$ by using $p$-adic continuity of polynomial functions on $\mathbf Q$. This also came up in another math.stackexchange post here and is described in general terms here.

An application to linear recursions taking on specific values (very similar to what Alex gives in his answer) is here and an interpretation of the result in terms of solving the exponential Diophantine equation $3^m = 1 + 2x^2$ is in the appendix here. Another application along the same lines, for integral solutions of the Diophantine equation $x^3 - 2y^3 = 1$, is here.

A use of $p$-adics to explain the structure of $(\mathbf Z/p^k\mathbf Z)^\times$ for odd primes $p$ (that it is cyclic for all $k \geq 1$) is here. The key point is to rewrite the group as a quotient of actual multiplicative groups $\mathbf Z_p^\times/(1 + p^k\mathbf Z_p)$ so that the multiplicative structure of $\mathbf Z_p^\times$ can be exploited. It is intriguing that to explain the behavior of a finite abelian group we pass to a $p$-adic compact group like $\mathbf Z_p^\times$, study it, and then take its quotient by an open subgroup. In the language of elementary number theory, this problem would be about showing odd prime-power moduli have a "primitive root" (old-fashioned terminology for a generator of the units for some modulus).

While not an actual use of $p$-adic completions, a cute use of an extended form of the $p$-adic absolute value is a proof of Gauss' lemma in $\mathbf Z[x]$: if a polynomial in $\mathbf Z[x]$ is reducible in $\mathbf Q[x]$ then it is reducible in $\mathbf Z[x]$ with factors of the same degrees as in $\mathbf Q[x]$. The idea of the $p$-adic proof is to extend the $p$-adic absolute value from $\mathbf Q$ to $\mathbf Q[x]$. See here.

One of the standard proofs that the harmonic sums $H_n = 1 + 1/2 + \cdots + 1/n$ are not integers for $n \geq 2$ is by showing these rational numbers are not $2$-adically integral (there is a unique term of largest $2$-adic size greater than $1$). See here.

In Koblitz's book on $p$-adic analysis and zeta-functions, he uses $p$-adic integration to explain $p$-power congruence properties of Bernoulli numbers that had been proved by Kummer, Clausen, and von Staudt in the 19th century by completely different methods.