Maths Olympiad Prep

Library / Saudi Arabian Mathematical Competitions /155 of 395

Saudi Arabian Mathematical Competitions, 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 0≤k≤p20 \leq k \leq p^{2} and p2p^{2} divides k(k+1)(k+2)⋯(k+p−3)−1k(k+1)(k+2) \cdots(k+p-3)-1.

Solution

Assume that there exists an integer kk such that 0≤k≤p20 \leq k \leq p^{2} and p2p^{2} divides k(k+1)(k+2)⋯(k+p−3)−1k(k+1)(k+2) \cdots(k+p-3)-1. Because pp does not divide any of the p−2p-2 consecutive integers k,(k+1),(k+2),…,(k+p−3)k,(k+1),(k+2), \ldots,(k+p-3), either k≡1k \equiv 1 or 2 mod p2 \bmod p. If k≡2 mod pk \equiv 2 \bmod p then, by Wilson's theorem,
k(k+1)(k+2)⋯(k+p−3)−1≡(p−1)!−1≡−2≢0 mod p. k(k+1)(k+2) \cdots(k+p-3)-1 \equiv (p-1)!-1 \equiv -2 \not \equiv 0 \bmod p.
We deduce that k≡1 mod pk \equiv 1 \bmod p.

On the other hand, we know from Wilson's theorem that (p−2)!−1≡0 mod p(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
(p−2)!−1≡i0p mod p2. (p-2)!-1 \equiv i_{0} p \bmod p^{2}.
Let k=ip+1k = i p + 1 for some integer i∈{0,1,…,p−1}i \in \{0,1, \ldots, p-1\}. We have
k(k+1)(k+2)⋯(k+p−3)−1≡(ip+1)(ip+2)⋯(ip+p−2)−1≡(p−2)!−1+ip∑j=1p−2(p−2)!j mod p2 \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=1p−2(p−2)!j≡(p−2)!∑j=1p−2j−1≡∑j=1p−2j≡(p−2)(p−1)2≡1 mod p \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+p−3)−1≡(i0+i)p mod p2. 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+p−3)−1≡0 mod p2k(k+1)(k+2) \cdots(k+p-3)-1 \equiv 0 \bmod p^{2} only for k=(p−i0)p+1k = (p-i_{0}) p + 1.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.