Maths Olympiad Prep

Library / /53 of 133

, 2015

Number theory Difficulty 5.4 AIME, harder Prove it Saudi Arabia

Let pp be an odd prime number. Prove that there exists a unique integer kk such that 0kp20 \leq k \leq p^{2} and p2p^{2} divides k(k+1)(k+2)(k+p3)1k(k+1)(k+2) \cdots(k+p-3)-1.

Solution

Assume that there exists an integer kk such that 0kp20 \leq k \leq p^{2} and p2p^{2} divides k(k+1)(k+2)(k+p3)1k(k+1)(k+2) \cdots(k+p-3)-1. Because pp does not divide any of the p2p-2 consecutive integers k,(k+1),(k+2),,(k+p3)k,(k+1),(k+2), \ldots,(k+p-3), either k1k \equiv 1 or 2modp2 \bmod p. If k2modpk \equiv 2 \bmod p then, by Wilson's theorem,
k(k+1)(k+2)(k+p3)1(p1)!12≢0modp. k(k+1)(k+2) \cdots(k+p-3)-1 \equiv (p-1)!-1 \equiv -2 \not \equiv 0 \bmod p.
We deduce that k1modpk \equiv 1 \bmod p.

On the other hand, we know from Wilson's theorem that (p2)!10modp(p-2)!-1 \equiv 0 \bmod p. This means that there exists a unique integer i0{1,,p}i_{0} \in \{1, \ldots, p\} such that
(p2)!1i0pmodp2. (p-2)!-1 \equiv i_{0} p \bmod p^{2}.
Let k=ip+1k = i p + 1 for some integer i{0,1,,p1}i \in \{0,1, \ldots, p-1\}. We have
k(k+1)(k+2)(k+p3)1(ip+1)(ip+2)(ip+p2)1(p2)!1+ipj=1p2(p2)!jmodp2 \begin{aligned} k(k+1)(k+2) \cdots(k+p-3)-1 &\equiv (i p+1)(i p+2) \cdots(i p+p-2)-1 \\ &\equiv (p-2)!-1 + i p \sum_{j=1}^{p-2} \frac{(p-2)!}{j} \bmod p^{2} \end{aligned}
and
j=1p2(p2)!j(p2)!j=1p2j1j=1p2j(p2)(p1)21modp \sum_{j=1}^{p-2} \frac{(p-2)!}{j} \equiv (p-2)! \sum_{j=1}^{p-2} j^{-1} \equiv \sum_{j=1}^{p-2} j \equiv \frac{(p-2)(p-1)}{2} \equiv 1 \bmod p
We deduce that
k(k+1)(k+2)(k+p3)1(i0+i)pmodp2. k(k+1)(k+2) \cdots(k+p-3)-1 \equiv (i_{0}+i) p \bmod p^{2}.
This proves that k(k+1)(k+2)(k+p3)10modp2k(k+1)(k+2) \cdots(k+p-3)-1 \equiv 0 \bmod p^{2} only for k=(pi0)p+1k = (p-i_{0}) p + 1.

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.