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

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.

I am not sure if the Gauss (Legendre) result qualifies as "the most delightful application of the $p$-adic numbers", but it gives that $$ n=a^2+b^2+c^2 $$ is the sum of three squares if and only if $$ -n \text{ is a square in } \Bbb Q_2. $$ Of course, this says that $n$ is not of the form $4^l(8k+7)$.

Edit: I realised that you already know this application. So I looked out for other applications. This MO-post refers to elementary results specifically. Some of them are in elementary number theory.

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.