Kvant Math Problem 442

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m02s
Source on kvant.digital

Problem

Let $p \gt 2$ be a prime number. For each $k$ from $1$ to $p-1$, denote by $a_k$ the remainder when the number $k^p$ is divided by $p^2$. Prove that $$a_1+a_2+a_3+\ldots+a_{p-1}=(p^3 - p^2)/2.$$

S. Okhitin

Exploration

For small primes the structure is very rigid. Take $p=3$. Then

$1^3=1,\quad 2^3=8 \equiv 8 \pmod 9.$

So $a_1=1$, $a_2=8$, and the sum equals $9$, which matches $(27-9)/2=9$.

For $p=5$,

$1^5=1,\ 2^5=32,\ 3^5=243,\ 4^5=1024.$

Reducing mod $25$ gives

$1,,7,,18,,24,$

whose sum is $50$, matching $(125-25)/2=50$.

The numerical pattern suggests a pairing phenomenon producing constant contributions equal to $p^2$. The natural pairing is $k$ with $p-k$, since binomial expansions of $(p-k)^p$ strongly resemble $(-k)^p$ modulo high powers of $p$. The key point to test is whether $k^p+(p-k)^p$ is divisible by $p^2$; if so, each pair contributes exactly $p^2$ as a sum of remainders.

The main risk is whether reduction modulo $p^2$ could introduce carry effects, so it is necessary to confirm that the paired sum is strictly between $p^2$ and $2p^2$ or exactly a multiple of $p^2$.

Problem Understanding

This is a Type B problem: prove a closed identity for a sum of residues.

We are given a prime $p>2$ and define $a_k$ as the remainder of $k^p$ upon division by $p^2$ for $1 \le k \le p-1$. The goal is to compute

$\sum_{k=1}^{p-1} a_k = \frac{p^3-p^2}{2}.$

The structure suggests pairing $k$ with $p-k$, since symmetry in binomial expansions modulo powers of $p$ typically produces cancellation at order $p^2$. The expected outcome is that each pair contributes exactly $p^2$, and there are $(p-1)/2$ such pairs.

Proof Architecture

The first lemma establishes that for every integer $k$ with $1 \le k \le p-1$, the number $k^p + (p-k)^p$ is divisible by $p^2$, obtained by a full binomial expansion of $(p-k)^p$.

The second lemma shows that if two integers in $[0,p^2-1]$ have a sum divisible by $p^2$, then their sum equals either $0$ or $p^2$, and excludes the zero case for the present residues.

The third step pairs indices $k$ and $p-k$ and sums all contributions, converting the full sum into a multiple of $p^2$ times the number of pairs.

The delicate point is the divisibility by $p^2$, since a naive reduction modulo $p$ is insufficient; the binomial coefficients must be tracked carefully to ensure at least two powers of $p$ appear in every term.

Solution

Fix a prime $p>2$ and an integer $k$ with $1 \le k \le p-1$. Consider the binomial expansion

$(p-k)^p = \sum_{i=0}^{p} \binom{p}{i} p^{p-i} (-k)^i.$

For $i \le p-2$, the factor $p^{p-i}$ contains at least $p^2$ because $p-i \ge 2$. Hence every term with $i \le p-2$ is divisible by $p^2$.

For $i=p-1$, we use $\binom{p}{p-1}=p$, and the corresponding term equals

$p \cdot p \cdot (-k)^{p-1} = p^2 (-k)^{p-1},$

which is also divisible by $p^2$.

The term $i=p$ equals $(-k)^p$ and is not necessarily divisible by $p^2$. Therefore

$(p-k)^p \equiv (-k)^p \pmod{p^2},$

and since $p$ is odd,

$(-k)^p = -k^p.$

Hence

$k^p + (p-k)^p \equiv k^p - k^p \equiv 0 \pmod{p^2},$

so $p^2$ divides $k^p + (p-k)^p$.

Now define $a_k$ as the remainder of $k^p$ modulo $p^2$, so $a_k \in {0,1,\dots,p^2-1}$. Since $1 \le k \le p-1$, neither $k^p$ nor $(p-k)^p$ is divisible by $p^2$, so both $a_k$ and $a_{p-k}$ are nonzero.

From $k^p + (p-k)^p \equiv 0 \pmod{p^2}$ it follows that

$a_k + a_{p-k} \equiv 0 \pmod{p^2}.$

Since $0 < a_k, a_{p-k} < p^2$, their sum lies strictly between $2$ and $2p^2-2$. The only multiple of $p^2$ in this interval is $p^2$, hence

$a_k + a_{p-k} = p^2.$

The integers $1,2,\dots,p-1$ split into $(p-1)/2$ disjoint pairs ${k,p-k}$. Summing over all pairs gives

$\sum_{k=1}^{p-1} a_k = \frac{p-1}{2} \cdot p^2 = \frac{p^3-p^2}{2}.$

This completes the proof. ∎

Verification of Key Steps

The critical divisibility argument hinges on confirming that every term in the binomial expansion of $(p-k)^p$ except the final one contains at least two factors of $p$. For $i \le p-2$, the exponent $p-i$ satisfies $p-i \ge 2$, guaranteeing a factor $p^2$ directly from $p^{p-i}$. For $i=p-1$, the binomial coefficient contributes one factor of $p$ and the remaining explicit $p^{p-(p-1)}=p$ contributes the second, ensuring divisibility by $p^2$.

The second delicate point is the transition from congruence modulo $p^2$ to equality of remainders. Since $a_k$ and $a_{p-k}$ are defined as least nonnegative residues, each lies strictly below $p^2$, forcing their sum to be the unique multiple of $p^2$ in its admissible range, namely $p^2$.

The pairing argument requires that the involution $k \mapsto p-k$ has no fixed points in ${1,\dots,p-1}$, which holds because $p$ is odd, ensuring $k=p-k$ would imply $2k=p$, impossible for integer $k$.

Alternative Approaches

One alternative approach uses Fermat quotients $q_p(k)=\frac{k^{p-1}-1}{p}$ to express $k^p = k + pkq_p(k)$ and then sums over $k$, reducing the problem to evaluating a symmetric sum of Fermat quotients modulo $p$. This method leads to the same final value but requires additional known identities about $\sum k q_p(k)$.

The pairing argument is preferable because it avoids any arithmetic of Fermat quotients and reduces the problem directly to a structural symmetry modulo $p^2$, making the divisibility mechanism transparent and self-contained.