IMO 2003/B3 solution

IMO 2003

Problem B3

Show that for each prime p, there exists a prime q such that n^p - p is not divisible by q for any positive integer n.

Solution

Thanks to Li Yi

If p = 2, then we can take q = 3, since squares cannot be 2 mod 3. So suppose p is odd.

Consider N = 1 + p + p² + ... + p^p-1. There are p terms. Since p is odd, that means an odd number of odd terms, so N is odd. Also N = p + 1 mod p², which is not 1 mod p², so N must have a prime factor q which is not 1 mod p². We will show that q has the required property.

Since N = 1 mod p, p does not divide N, so q cannot be p. If p = 1 mod q, then N = 1 + 1 + ... + 1 = p mod q. Since N = 0 mod q, that implies q divides p. Contradiction. So q does not divide p - 1.

Now suppose n^p = p mod q (*). We have just shown that n cannot be 1 mod q. We have also shown that q is not p, so n cannot be a multiple of q. So assume n is not 0 or 1 mod q. Take the pth power of both sides of (*). Since (p - 1)N = p^p - 1, we have p^p = 1 mod q. So n to the power of p² is 1 mod q. But n^q-1 = 1 mod q (the well-known Fermat little theorem). So if d = gcd(q-1, p²), then n^d = 1 mod q. We chose q so that q-1 is not divisible by p², so d must be 1 or p. But we are assuming n is not 1 mod q, so d cannot be 1. So it must be p. In other words, n^p = 1 mod q. But n^p = p mod q, so p = 1 mod q. Contradiction (we showed above that q does not divide p - 1).

44th IMO 2003