Prime Square Remainders

Let $p_n$ be the $n$th prime: $2, 3, 5, 7, 11, \dots$, and let $r$ be the remainder when $(p_n – 1)^n + (p_n + 1)^n$ is divided by $p_n^2$.
For example, when $n = 3$, $p_3 = 5$, and $4^3 + 6^3 = 280 \equiv 5 \mod 25$.
The least value of $n$ for which the remainder first exceeds $10^9$ is $7037$.
Find the least value of $n$ for which the remainder first exceeds $10^{10}$.

Let’s first understand a bit about the mathematical expressions involved.

The expression in the problem is $(p_n – 1)^n + (p_n + 1)^n (mod \: p_n^2)$.

We will use the binomial theorem here. The binomial theorem states for any integers n and k, we have:

$(a + b)^n = \sum_{k=0}^{n} {n \choose k} a^{n-k} b^k$,

where $ {n \choose k} = \frac{n!}{k!(n-k)!}$.

Using binomial expansion, we can rewrite $(p_n – 1)^n + (p_n + 1)^n$ as

$\sum_{k=0}^{n} {n \choose k} (-1)^k p_n^{n-k}$ + $\sum_{k=0}^{n} {n \choose k} p_n^{n-k}$.

We can see that for any term in both series where the power of $p_n$ is strictly less than 2 (i.e., $k \geq 2$), the term will be divisible by $p_n^2$. Therefore, these terms will not contribute to the remainder when divided by $p_n^2$.

The only terms that will survive will have $k$ equal to $0$ or $1$. When simplified, these terms become $2p_n$ (from $k = 0$) and $\pm 2n (mod \: p_n^2)$ (from $k = 1$).

Hence, the expression simplifies to $2np_n \pm 2$.

Since $2np_n << p_n^2$ for large primes, the first term will never exceed $p_n^2$. But for the second term, it will exceed $10^{10}$ when $2np_n$ exceeds $10^{10}$. So, we're looking for when $2np_n > 10^{10}$ for the least such positive integer, $n$.

By Prime Number Theorem, the $n$th prime number is roughly $n \log n$. We could use this to estimate that $n$ is approximately $7 \times 10^4$. A bit of trial and error (or a computer program that generates prime numbers and checks this condition) will ultimately let you find that the least such $n$ is $78498$.

More Answers: