IMO 2004 SL N6

Origin: IRE | Category: Number Theory

Problem

Given an integer n > 1, denote by Pn the product of all positive integers x less than n and such that n divides x2 −1. For each n > 1, ﬁnd the remainder of Pn on division by n.

Solution

Let Sn = {x \inN | x \leqn, n | x2 −1}. It is easy to check that Pn \equiv1 (mod n) for n = 2 and Pn \equiv−1 (mod n) for n \in{3, 4}, so from now on we assume n > 4. We note that if x \inSn, then also n−x \inSn and (x, n) = 1. Thus Sn splits into pairs {x, n −x}, where x \inSn and x \leqn/2. In each of these pairs the product of elements gives remainder −1 upon division by n. Therefore Pn \equiv(−1)m, where Sn has 2m elements. It remains to ﬁnd the parity of m. Suppose ﬁrst that n > 4 is divisible by 4. Whenever x \inSn, the numbers |n/2−x|, n−x, n−|n/2−x| also belong to Sn (indeed, n | (n/2−x)2−1 = n2/4 −nx + x2 −1 because n | n2/4, etc.). In this way the set Sn splits into four-element subsets {x, n/2 −x, n/2 + x, n −x}, where x \inSn and x < n/4 (elements of these subsets are diﬀerent for x ̸= n/4, and n/4 doesn’t belong to Sn for n > 4). Therefore m = |Sn|/2 is even and Pn \equiv1 (mod m). Now let n be odd. If n | x2 −1 = (x −1)(x + 1), then there exist natural numbers a, b such that ab = n, a | x −1, b | x + 1. Obviously a and b are coprime. Conversely, given any odd a, b \inN such that (a, b) = 1 and ab = n, by the Chinese remainder theorem there exists x \in{1, 2, . . ., n−1} such that a | x−1 and b | x+1. This gives a bijection between all ordered pairs (a, b) with ab = n and (a, b) = 1 and the elements of Sn. Now if n = p\alpha1 1 \cdot \cdot \cdot p\alphak k is the decomposition of n into primes, the number of pairs (a, b) is equal to 2k (since for every i, either p\alphai i | a or p\alphai i | b), and hence

m = 2k−1. Thus Pn \equiv−1 (mod n) if n is a power of an odd prime, and Pn \equiv1 otherwise. Finally, let n be even but not divisible by 4. Then x \inSn if and only if x or n −x belongs to Sn/2 and x is odd. Since n/2 is odd, for each x \inSn/2 either x or x + n/2 belongs to Sn, and by the case of n odd we have Sn \equiv\pm1 (mod n/2), depending on whether or not n/2 is a power of a prime. Since Sn is odd, it follows that Pn \equiv−1 (mod n) if n/2 is a power of a prime, and Pn \equiv1 otherwise. Second solution. Obviously Sn is closed under multiplication modulo n. This implies that Sn with multiplication modulo n is a subgroup of Zn, and therefore there exist elements a1 = −1, a2, . . . , ak \inSn that generate Sn. In other words, since the ai are of order two, Sn consists of products $ i\inA ai, where A runs over all subsets of {1, 2, . . ., k}. Thus Sn has 2k elements, and the product of these elements equals Pn \equiv(a1a2 \cdot \cdot \cdot ak)2k−1 (mod n). Since a2 i \equiv1 (mod n), it follows that Pn \equiv1 if k \geq2, i.e., if |Sn| > 2. Otherwise Pn \equiv−1 (mod n). We note that |Sn| > 2 is equivalent to the existence of a \inSn with 1 < a < n−1. It is easy to ﬁnd that such an a exists if and only if neither of n, n/2 is a power of an odd prime.