IMO 1993 SL 10

Origin: IND

Problem

A natural number n is said to have the property P if whenever n divides an −1 for some integer a, n2 also necessarily divides an −1. (a) Show that every prime number has property P. (b) Show that there are infinitely many composite numbers n that possess property P.

Solution

(a) Let n = p be a prime and let p | ap −1. By Fermat’s theorem p | ap−1 −1, so that p | agcd(p,p−1) −1 = a −1, i.e., a \equiv1 (mod p). Since then ai \equiv1 (mod p), we obtain p | ap−1 + \cdot \cdot \cdot + a + 1 and hence p2 | ap −1 = (a −1)(ap−1 + \cdot \cdot \cdot + a + 1). (b) Let n = p1 \cdot \cdot \cdot pk be a product of distinct primes and let n | an −1. Then from pi | an −1 = (a(n/pi))pi −1 and part (a) we conclude that p2 i | an −1. Since this is true for all indices i, we also have n2 | an −1; hence n has the property P.