Find all positive integers n > 1 such that if a and b are relatively prime then a = b mod n iff ab = 1 mod n.
Solution
Answer: 2, 3, 4, 6, 8, 12, 24.
Since a = b mod n, the condition is equivalent to a2 = 1 mod n for all a relatively prime to n. Suppose n = ∏ pe(p), then we claim that a2 = 1 mod n for all a relatively prime to n iff a2 = 1 mod pe(p) mod pe(p) for each prime factor p of n (and a relatively prime to p). The if part is obvious: if a is relatively prime to n, then it is relatively prime to each pe(p), so a2 = 1 mod pe(p), so a2 = 1 mod n. To prove the only if part, suppose a is relatively prime to p. Let r, s, ... be the primes dividing n which do not divide a. Then a + pe(p)(rs...) is relatively prime to n. So (a + pe(p)(rs...) )2 = 1 mod n. So it must also be 1 mod pe(p). But (a + pe(p)(rs...) )2 = a2 mod pe(p), so a2 = 1 mod pe(p) as required.
It is easy to check that a2 = 1 mod 8 for any odd integer a. Hence also a2 = 1 mod 2 and mod 4 for any odd integer a. But 32 = 9, which is not 1 mod 2k for k > 3. Similarly, it is easy to check that 12 = 22 = 1 mod 3, but 22 = 4, which is not 1 mod 3k for k > 1. Finally 22 = 4, which is not 1 mod pk for p > 3. So n cannot be divisible by any primes except 2 and 3, and it is not divisible by 16 or 9. On the other hand, if n = 2h3k with h = 0, 1, 2 or 3 and k = 0 or 1, then we have established that a2 = 1 mod 2h for any a relatively prime to 2, and a2 = 1 mod 3k for any a relatively prime to k, so that a2 = 1 mod n for any a relatively prime to n.
∏ John Scholes
jscholes@kalva.demon.co.uk
10 Oct 2002