IMO 2000 SL N1

Origin: JAP | Category: Number Theory

Problem

Determine all positive integers n \geq2 that satisfy the following condition: For all integers a, b relatively prime to n, a \equivb (mod n) if and only if ab \equiv1 (mod n).

Solution

The given condition is obviously equivalent to a2 \equiv1 (mod n) for all inte- gers a coprime to n. Let n = p\alpha1 1 p\alpha2 2 \cdot \cdot \cdot p\alphak k be the factorization of n onto primes. Since by the Chinese remainder theorem the numbers coprime to n can give any remainder modulo p\alphai i except 0, our condition is equivalent to a2 \equiv1 (mod p\alphai i ) for all i and integers a coprime to pi. Now if pi \geq3, we have 22 \equiv1 (mod p\alphai i ), so pi = 3 and \alphai = 2. If pj = 2, then 32 \equiv1 (mod 2\alphaj) implies \alphaj \leq3. Hence n is a divisor of 23 \cdot 3 = 24. Conversely, each n | 24 has the desired property.