Maths Olympiad Prep

Library / /60 of 120

Number theory Difficulty 5.3 AIME, harder Prove it Saudi Arabia

Let p3p \geq 3 be a prime. For j=1,2,,p1j=1,2, \ldots, p-1, let rjr_{j} be the remainder when the integer jp11p\frac{j^{p-1}-1}{p} is divided by pp. Prove that
r1+2r2++(p1)rp1p+12(modp) r_{1}+2 r_{2}+\ldots+(p-1) r_{p-1} \equiv \frac{p+1}{2}(\bmod p)

Solution

For j=1,2,,p1j=1,2, \ldots, p-1, we have
jp11p=ajp+rj \frac{j^{p-1}-1}{p}=a_{j} p+r_{j}
for some integer aja_{j}. It follows
jpjp=jajp+jrj, \frac{j^{p}-j}{p}=j a_{j} p+j r_{j},
hence
jpj+(pj)p(pj)p=jajp+jrj+(pj)apjp+(pj)rpj. \frac{j^{p}-j+(p-j)^{p}-(p-j)}{p}=j a_{j} p+j r_{j}+(p-j) a_{p-j} p+(p-j) r_{p-j}.
We obtain
jp+(pj)pp=jajp+jrj+(pj)apjp+(pj)rpj+1. \frac{j^{p}+(p-j)^{p}}{p}=j a_{j} p+j r_{j}+(p-j) a_{p-j} p+(p-j) r_{p-j}+1.
Because
jp+(pj)p=(p0)pp(p1)pp1j++(pp1)pjp1 j^{p}+(p-j)^{p}=\binom{p}{0} p^{p}-\binom{p}{1} p^{p-1} j+\ldots+\binom{p}{p-1} p j^{p-1}
we obtain that p2jp+(pj)pp^{2} \mid j^{p}+(p-j)^{p} and we get for all j=1,2,,p1j=1,2, \ldots, p-1,
jrj+(pj)rpj+10(modp) j r_{j}+(p-j) r_{p-j}+1 \equiv 0 \quad(\bmod p)
Adding up all these relations it follows
2(r1+2r2++(p1)rp1)(p1)(modp) 2\left(r_{1}+2 r_{2}+\ldots+(p-1) r_{p-1}\right) \equiv-(p-1)(\bmod p)
hence
r1+2r2++(p1)rp1p+12(modp) r_{1}+2 r_{2}+\ldots+(p-1) r_{p-1} \equiv \frac{p+1}{2}(\bmod p)

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.