Maths Olympiad Prep

Library / /2 of 22

Number theory Difficulty 5.2 AIME, harder Prove it Czech-Polish-Slovak Mathematical Match

Determine all prime numbers pp, such that the number
(p1)2+(p2)2++(pp1)2 \binom{p}{1}^2 + \binom{p}{2}^2 + \dots + \binom{p}{p-1}^2
is divisible by p3p^3.

Solution

We start from the observation that for k=1,2,,pk = 1, 2, \dots, p we have
(p1k1)±1(modp).(1) \binom{p-1}{k-1} \equiv \pm 1 \pmod{p}. \qquad (1)
To see this, note that
p11(modp), p-1 \equiv -1 \pmod{p},
p22(modp), p-2 \equiv -2 \pmod{p},
\vdots \qquad \vdots
k(pk)(modp), k \equiv -(p-k) \pmod{p},
hence, multiplying,
(p1)!(k1)!±(pk)!(modp) \frac{(p-1)!}{(k-1)!} \equiv \pm(p-k)! \pmod{p}
and (1) follows. This can be written in an equivalent form
kp(pk)±1(modp), \frac{k}{p} \binom{p}{k} \equiv \pm 1 \pmod{p},
which implies that
(pk)=pakp±1k, \binom{p}{k} = p \cdot \frac{a_k p \pm 1}{k},
for some integer aka_k. Therefore, if pp satisfies the given conditions, we have
pk=1p1(akp±1)2k2, p \mid \sum_{k=1}^{p-1} \frac{(a_k p \pm 1)^2}{k^2},
or pk=1p11/k2p \mid \sum_{k=1}^{p-1} 1/k^2, where by 1/m1/m we understand the unique integer 1lp11 \le l \le p-1 satisfying ml1(modp)ml \equiv 1 \pmod{p}. Now observe that 1/k2(1/k)2(modp)1/k^2 \equiv (1/k)^2 \pmod{p} and
k=1p11k2k=1p1k2=p(p1)(2p1)6(modp), \sum_{k=1}^{p-1} \frac{1}{k^2} \equiv \sum_{k=1}^{p-1} k^2 = \frac{p(p-1)(2p-1)}{6} \pmod{p},
which is divisible by pp if and only if p5p \ge 5.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.