Given a prime $p$, show that \[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^4}.\] Timothy Chu.
Problem
Source: ELMO Shortlist 2010, N2
Tags: modular arithmetic, algebra, difference of squares, special factorizations, number theory proposed, number theory
applepi2000
04.09.2012 05:27
Zhero wrote: Given a prime $p$, show that \[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^4}.\] Timothy Chu. Typo edited Note that we have by difference of squares: \[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^4}\] \[\Leftrightarrow (\sum_{k=1}^{p-1}k^{-1})(p\sum_{k=1}^{p-1}k^{-1}+2)\equiv -p\sum_{k=1}^{p-1}k^{-2}\mod p^3\] Since $2\sum_{k=1}^{p-1}k^{-1}=\sum_{k=1}^{p-1}\frac{1}{k(p-k)}$ and $p\sum_{k=1}^{p-1}k^{-1}\equiv 0\mod p^2$, this is: \[\Leftrightarrow 2(\sum_{k=1}^{p-1}\frac{1}{k(p-k)})\equiv -2\sum_{k=1}^{p-1}k^{-2}\mod p^2\] \[\Leftrightarrow \sum_{k=1}^{p-1}(\frac{1}{k^2}+\frac{1}{k(p-k)})\equiv 0\mod p^2\] \[\Leftrightarrow \sum_{k=1}^{p-1}\frac{1}{k^2(p-k)}\equiv 0\mod p\] \[\Leftrightarrow \sum_{k=1}^{p-1}(\frac{1}{k})^3\equiv 0\mod p\] Which is true since \[\sum_{k=1}^{p-1}(\frac{1}{k})^3\equiv \sum_{k=1}^{p-1}k^3\equiv \frac{p^2(p+1)^2}{4}\equiv 0\mod p\] As desired.
proglote
04.09.2012 19:45
A bit different: let $S_k = \sum_{i=1}^{p-1} i^{-k}$. By Wolstenholme's we have $S_1 \equiv 0 \mod p^2$, therefore it remains to prove: \[1 + 2pS_1 \equiv 1-p^2 S_2 \pmod{p^4} \iff 2S_1 \equiv -pS_2 \pmod{p^3}.\] Note that $S_1 = p \sum_{i=1}^{(p-1)/2} \frac{1}{i(p-i)}$ and $S_2 = \sum_{i=1}^{(p-1)/2} \frac{p^2 - 2pi + 2i^2}{i^2 (p-i)^2}$ by pairing terms of the form $i$ and $p-i.$ Thus, the problem is reduced to \[2 \cdot \sum_{i=1}^{(p-1)/2} \frac{1}{i(p-i)} \equiv -\sum_{i=1}^{(p-1)/2} \frac{p^2 - 2pi + 2i^2}{i^2 (p-i)^2} \pmod{p^2} \\ \iff \sum_{i=1}^{(p-1)/2} \frac{1}{i(p-i)} \equiv \sum_{i=1}^{(p-1)/2} \frac{i(p-i)}{i^2 (p-i)^2} \pmod{p^2}, \] which is clear since both sides are equal.
proglote
04.09.2012 23:08
The following is also true: Given a prime $p>5$, show that \[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^5}.\]
AlastorMoody
13.04.2020 03:50
proglote wrote:
Given a prime $p>5$, show that \[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^5}.\]
Note
\begin{align*} \left( 1+ p \sum_{k=1}^{p-1} k^{-1} \right)^2 \equiv 1 -p^2 \sum_{k=1}^{p-1} k^{-2} \pmod{p^5} \end{align*}\begin{align*} \Longleftrightarrow \left( 1 +p\sum_{k=1}^{p-1} \frac{1}{k} \right)^2 = p^2 \left( \sum_{k=1}^{p-1} \frac{1}{k} \right)^2 +1 +2p \sum_{k=1}^{p-1} \frac{1}{k} \equiv 1-p^2 \sum_{k=1}^{p-1} \frac{1}{k^2} \pmod{p^5} \end{align*}\begin{align*} \Longleftrightarrow p \sum_{k=1}^{p-1} \frac{1}{k^2} + 2 \sum_{k=1}^{p-1} \frac{1}{k} \equiv 0 \pmod{p^4} \end{align*}\begin{align*} \Longleftrightarrow p \sum_{k=1}^{p-1} \frac{1}{k^2} + 2p \sum_{k=1}^{\tfrac{p-1}{2}} \frac{1}{k (p-k)} \equiv 0 \pmod{p^4} \end{align*}\begin{align*} \Longleftrightarrow \sum_{k=1}^{p-1} \frac{1}{k^2} + \sum_{k=1}^{p-1} \frac{1}{k(p-k)} \equiv 0 \pmod{p^3} \end{align*}\begin{align*} \Longleftrightarrow \sum_{k=1}^{p-1} \frac{1}{k^2 (p-k)} \equiv 0 \pmod{p^2} \end{align*}\begin{align*} \Longleftrightarrow \sum_{k=1}^{\tfrac{p-1}{2}} \left( \frac{1}{k^2 (p-k)} + \frac{1}{(p-k)^2 k} \right) \equiv 0 \pmod{p^2} \end{align*}\begin{align*} \Longleftrightarrow \sum_{k=1}^{\tfrac{p-1}{2}} \left( \frac{1}{k(p-k)} \right)^2 \equiv 0 \pmod{p} \end{align*}\begin{align*} \Longleftrightarrow \sum_{k=1}^{p-1} k^{-4} \equiv \sum_{k=1}^{p-1} k^4 \equiv 0 \pmod{p} \qquad \blacksquare \end{align*}
Aryan-23
05.07.2020 13:02
Write $S_1 \overset {\text {def}}{=} \frac{1}{1}+..+\frac{1}{p-1}$ and $S_2 \overset {\text {def}}{=} \frac{1}{1^2}+...+\frac{1}{(p-1)^2}$.
The problem asks for $p^2 S_1^2 + 2pS_1 + p^2 S_2 \equiv 0 \pmod {p^5}$
Clearly $p^2 S_1^2 \equiv 0 \pmod {p^5}$ (By Wolstenholme) so it remains to show $2S_1 + pS_2 \equiv 0$ mod $p^4$
Now we note $$2S_1 = \frac{1}{1} + \frac{1}{p-1} + \frac{1}{2}+\frac{1}{p-2}+ \dots$$
$$\implies 2S_1 =\frac{p}{1(p-1)}+\frac{p}{2(p-2)} + \dots $$
It remains to show that $\frac{1}{1(p-1)}+\frac{1}{2(p-2)}+ \dots +S_2 \equiv 0 \pmod {p^3}$.
Grouping terms ,we wish to show :
$\sum \frac{1}{k^2(p-k)}\equiv 0 \pmod {p^3}$.
Since $\frac{1}{k^2(p-k)}+\frac{1}{(p-k)^2k} = \frac{p}{k^2(p-k)}$,
We wish to show
$$\frac{1}{1^2(p-1)}+\dots+\frac{1}{(p-1)^21} \equiv 0 \pmod {p^2}$$Grouping opposite terms, we need
$$\frac{p}{1^2(p-1)^2} + \dots + \frac{p}{(p-1)^21^2} \equiv 0 \pmod {p^2}$$
$$ \iff \displaystyle\sum \frac{1}{k^4} \equiv 0 \pmod p $$
$$ \iff \displaystyle\sum k^4 \equiv 0 \pmod {p}$$
which is trivially true as $\{k^4\}_{k=1}^{p-1}$ forms a permutation of $\{1,2, \dots p-1\}$ .
Wish Granted
WolfusA
05.07.2020 15:01
Missing cherry on top identity for extension proof. So obvious, but nobody has written it? $$\sum_{k=1}^nk^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$$
Sprites
17.09.2021 09:42
Zhero wrote: Given a prime $p$, show that \[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^4}.\] Timothy Chu.
Manipulating,\[\left(1+p\sum_{k=1}^{p-1}k^{-1}\right)^2 \equiv 1-p^2\sum_{k=1}^{p-1}k^{-2} \pmod{p^4}\]\[ \Leftrightarrow \sum_{i=1}^{p-1} i^{-1} \left(p\sum_{i=1}^{p-1} i^{-1}+2 \right) \equiv -p \sum_{j=1}^{p-1}k^{-2} \pmod {p^3}\]Lemma: $p|\sum_{i=1}^{p-1} i^{-1}$(more specifically if $A+B=p$ then $p|A^{-1}+B^{-1}$)
By the above lemma,$p^2|p\sum_{k=1}^{p-1}k^{-1}$,now we just need to manipulate it to get:
\[\Leftrightarrow 2 \left(\sum_{k=1}^{p-1}\frac{1}{k(p-k)}\right)\equiv -2\sum_{k=1}^{p-1}k^{-2}\pmod p^2\]\[\Leftrightarrow \sum_{k=1}^{p-1}\left(\frac{1}{k^2}+\frac{1}{k(p-k)}\right)\equiv 0 \pmod {p^2}\]\[\Leftrightarrow \sum_{k=1}^{p-1}\frac{1}{k^2(p-k)}\equiv 0\pmod p\]\[\Leftrightarrow \sum_{k=1}^{p-1}\left(\frac{-1}{k}\right)^3\equiv 0\pmod p\]which is obvious so we are done.