Maths Olympiad Prep

Library / Bulgarian National Mathematical Olympiad /1 of 15

Bulgarian National Mathematical Olympiad

Number theory Difficulty 5.5 AIME, harder Prove it Bulgaria

Find all primes pp and all positive integers aa and mm such that a≤5p2a \le 5p^2 and (p−1)!+a=pm(p-1)! + a = p^m.

Solution

Answer: (p,a,m)=(2,1,1),(2,3,2),(2,7,3),(3,1,1),(3,7,2),(3,25,3),(5,1,2),(2,15,4),(5,101,3)(p, a, m) = (2, 1, 1), (2, 3, 2), (2, 7, 3), (3, 1, 1), (3, 7, 2), (3, 25, 3), (5, 1, 2), (2, 15, 4), (5, 101, 3).
Direct checks for p=2,3,5p = 2, 3, 5 give the above solutions.
For p≥7p \ge 7 the Wilson theorem implies a≡1(modp)a \equiv 1 \pmod p. Moreover, obviously p−1∣a−1p-1|a-1. Therefore a=kp(p−1)+1a = kp(p-1)+1 for some integer k≥0k \ge 0. If k≥6k \ge 6 then a≥6p2−6p+1>5p2a \ge 6p^2 - 6p + 1 > 5p^2, a contradiction. So we have 0≤k≤50 \le k \le 5.
After division by p−1p-1 we obtain
(p−2)!+kp=pm−1+pm−2+⋯+1. (p-2)! + kp = p^{m-1} + p^{m-2} + \dots + 1.
Since p≥7p \ge 7, the 22 and p−12\frac{p-1}{2} are different and appear in (p−2)!(p-2)!, i.e. p−1∣(p−2)!p-1|(p-2)!. This gives k≡m(modp−1)k \equiv m \pmod{p-1}.
If m≥pm \ge p, then
(p−2)!+kp=pm−1+pm−2+⋯+1>pp−1>(p−1)!, (p-2)! + kp = p^{m-1} + p^{m-2} + \dots + 1 > p^{p-1} > (p-1)!,
which easily gives a contradiction. Thus m≤p−1m \le p-1.
If k=0k=0, then m=p−1m = p-1 and
(p−2)!=pm−1≥pp−1−1>(p−1)p−1>(p−1)!, (p-2)! = p^m - 1 \ge p^{p-1} - 1 > (p-1)^{p-1} > (p-1)!,
a contradiction. If k=1k=1 or 22, then m=1m=1 or 22, respectively, which is impossible. If k=3k=3, then m=3m=3, i.e. (p−2)!=(p−1)2(p-2)! = (p-1)^2, which is impossible.
For k=4k=4 we get m=4m=4 and (p−2)!=(p−1)(p2+2p−1)(p-2)! = (p-1)(p^2+2p-1), whence
p−2∣p2+2p−1=p2−4+2(p−2)+7, p-2|p^2+2p-1 = p^2-4+2(p-2)+7,
i.e. p=7p=7, which does not give solutions. For k=5k=5 we obtain m=5m=5 and (p−2)!=(p−1)(p3+2p2+3p−1)(p-2)! = (p-1)(p^3+2p^2+3p-1), whence
p−2∣p3+2p2+3p−1=p3−8+2(p2−4)+3(p−2)+21, p-2|p^3+2p^2+3p-1 = p^3-8+2(p^2-4)+3(p-2)+21,
i.e. p=7p=7, which does not give solutions.

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.