42nd IMO shortlist 2001/N4 solution

42nd IMO 2001 shortlist

Problem N4

Let p > 3 be a prime. Show that there is a positive integer n < p-1 such that n^p-1 - 1 and (n+1)^p-1 - 1 are not divisible by p².

Solution

By the binomial theorem we have (p - a)^p-1 - a^p-1 = (p-1) p a^p-1 mod p². For 0 < a < p, (p-1) p a = p mod p², so (p - a)^p-1 and a^p-1 are unequal mod p². Hence at most one of them is 0 mod p². In particular, since 1² = 1 mod p², we must have (p-1)^p-1 ≠ 1 mod p². Also, at least (p-3)/2 of 2, 3, ... , p-2 must have p-1th powers ≠ 1 mod p². So either one of the pairs (2, 3), (4, 5), ... , (p-3, p-2) has both members with p-1th powers ≠ 1 mod p², in which case we are done, or exactly one member of each pair has p-1th power ≠ 1 mod p².

Now if p-2 has p-1th power ≠ 1 mod p² then we are done (because of p-1). If not, then p-3 has p-1th power ≠ 1 mod p². Now suppose (p-4)^p-1 = 1 mod p². Then (expanding) 1 = 4^p-1 - (p-1)p 4^p-2 = 4^p-1 + p 4^p-2 mod p² (*). But (p-2)^p-1 = 1 mod p², so (expanding) 1 = 2^p-1 + p 2^p-2 mod p². Squaring, 1 = 4^p-1 + p 4^p-1 mod p². Subtracting from (*), 0 = p(4^p-1 - 4^p-2) = 3 p 4^p-2 mod p², but that is clearly false. So we must have (p-4)^p-1 ≠ 1 mod p² and we are home (with p-4 and p-3).

Comment. This is a weak result. There are relatively few a for which a^p-1 = 1 mod p².

42nd IMO shortlist 2001