Maths Olympiad Prep

Library / /499 of 520

Number theory Difficulty 7.4 National olympiad, round 2 Prove it

32. Let p>5,pp>5, p be a prime number. The function
fp(x)=k=1p11(px+k)2f_{p}(x)=\sum_{k=1}^{p-1} \frac{1}{(p x+k)^{2}}

Prove: For any x,yNx, y \in \mathbf{N}^{*}, when fp(x)fp(y)f_{p}(x)-f_{p}(y) is written as a simplest fraction, its numerator is a multiple of p3p^{3}.

Solution

32. Introduce the congruence notation: Use ba(modn)\frac{b}{a}(\bmod n) to denote ba1(modn)b a^{-1}(\bmod n), where a1a^{-1} is the modular inverse of aa modulo nn (note that this requires (a,n)=1(a, n)=1).

Notice that, under the above fractional congruence notation, we only need to prove: fp(x)fp(y)0(modp3)f_{p}(x)-f_{p}(y) \equiv 0\left(\bmod p^{3}\right). Since
fp(x)fp(y)=k=1p1(1(px+k)21(py+k)2)=k=1p1p2(y2x2)+p2k(yx)(px+k)2(py+k)2\begin{aligned} f_{p}(x)-f_{p}(y) & =\sum_{k=1}^{p-1}\left(\frac{1}{(p x+k)^{2}}-\frac{1}{(p y+k)^{2}}\right) \\ & =\sum_{k=1}^{p-1} \frac{p^{2}\left(y^{2}-x^{2}\right)+p \cdot 2 k(y-x)}{(p x+k)^{2}(p y+k)^{2}} \end{aligned}

Therefore, we only need to prove: \square
k=1p1p(y2x2)+2k(yx)(px+k)2(py+k)20(modp2).\sum_{k=1}^{p-1} \frac{p\left(y^{2}-x^{2}\right)+2 k(y-x)}{(p x+k)^{2}(p y+k)^{2}} \equiv 0\left(\bmod p^{2}\right) .

And
(px+k)2(py+k)2(2pxk+k2)(2pyk+k2)2pk3(x+y)+k4(modp2),\begin{aligned} (p x+k)^{2}(p y+k)^{2} & \equiv\left(2 p x k+k^{2}\right)\left(2 p y k+k^{2}\right) \\ & \equiv 2 p k^{3}(x+y)+k^{4}\left(\bmod p^{2}\right), \end{aligned}

Hence, to prove (10) holds, we only need to prove:
k=1p1p(y2x2)+2k(yx)2p(x+y)k3+k40(modp2)k=1p1(2(yx)k33p(y2x2)k4+2p(x+y)k3)0(modp2)\begin{aligned} & \sum_{k=1}^{p-1} \frac{p\left(y^{2}-x^{2}\right)+2 k(y-x)}{2 p(x+y) k^{3}+k^{4}} \equiv 0\left(\bmod p^{2}\right) \\ \Leftrightarrow & \sum_{k=1}^{p-1}\left(\frac{2(y-x)}{k^{3}}-\frac{3 p\left(y^{2}-x^{2}\right)}{k^{4}+2 p(x+y) k^{3}}\right) \equiv 0\left(\bmod p^{2}\right) \end{aligned}

Furthermore, we only need to prove the following congruences hold simultaneously:
{k=1p11k30(modp2)k=1p11k4+2p(x+y)k30(modp)\left\{\begin{array}{l} \sum_{k=1}^{p-1} \frac{1}{k^{3}} \equiv 0\left(\bmod p^{2}\right) \\ \sum_{k=1}^{p-1} \frac{1}{k^{4}+2 p(x+y) k^{3}} \equiv 0(\bmod p) \end{array}\right.

For (11), since
2k=1p11k3=k=1p1(1k3+1(pk)3)=k=1p1p33p2k+3pk2k3(pk)3k=1ρ13pk(pk)3(modp2)\begin{aligned} 2 \sum_{k=1}^{p-1} \frac{1}{k^{3}} & =\sum_{k=1}^{p-1}\left(\frac{1}{k^{3}}+\frac{1}{(p-k)^{3}}\right) \\ & =\sum_{k=1}^{p-1} \frac{p^{3}-3 p^{2} k+3 p k^{2}}{k^{3}(p-k)^{3}} \equiv \sum_{k=1}^{\rho-1} \frac{3 p}{k(p-k)^{3}}\left(\bmod p^{2}\right) \end{aligned}

Hence, we only need to prove: k=1p11k(pk)30(modp)\sum_{k=1}^{p-1} \frac{1}{k(p-k)^{3}} \equiv 0(\bmod p). By
k(pk)3k4(modp)k(p-k)^{3} \equiv-k^{4}(\bmod p)

We only need to prove: k=1p11k40(modp)\sum_{k=1}^{p-1} \frac{1}{k^{4}} \equiv 0(\bmod p). In fact, (12) also reduces to proving this.
Below, we prove: When p>5,pp>5, p is a prime, k=1p11k40(modp)\sum_{k=1}^{p-1} \frac{1}{k^{4}} \equiv 0(\bmod p).
By Lagrange's theorem, we know that x41(modp)x^{4} \equiv 1(\bmod p) has at most 4 solutions modulo pp, so there exists s{1,2,,p1}s \in\{1,2, \cdots, p-1\} such that s41(modp)s^{4} \neq 1(\bmod p).

Notice that, {1,12,,1p1}\left\{1, \frac{1}{2}, \cdots, \frac{1}{p-1}\right\} and {s,s2,,sp1}\left\{s, \frac{s}{2}, \cdots, \frac{s}{p-1}\right\} are both reduced residue systems modulo pp, thus,
k=1p11k4k=1p1(sk)4=s4k=1p11k4(modp)\sum_{k=1}^{p-1} \frac{1}{k^{4}} \equiv \sum_{k=1}^{p-1}\left(\frac{s}{k}\right)^{4}=s^{4} \sum_{k=1}^{p-1} \frac{1}{k^{4}}(\bmod p)

Thus, combining p(s41)p \nmid\left(s^{4}-1\right), we get k=1p11k40(modp)\sum_{k=1}^{p-1} \frac{1}{k^{4}} \equiv 0(\bmod p).
The proposition is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.