IMO 2012 Shortlist N6

Category: Number Theory

Problem

Let x and y be positive integers. If x2n − 1 is divisible by 2n y + 1 for every positive integer n, prove that x = 1. Solution. First we prove the following fact: For every positive integer y there exist infinitely many primes p ≡ 3 (mod 4) such that p divides some number of the form 2n y + 1. Clearly it is enough to consider the case y odd. Let 2y + 1 = pe1 1 ···per r be the prime factorization of 2y + 1. Suppose on the contrary that there are finitely many primes pr+1,...,pr+s ≡ 3 (mod 4) that divide some number of the form 2n y + 1 but do not divide 2y + 1. We want to find an n such that pei i ||2n y+1 for 1 ≤ i ≤ r and pi ∤ 2n y+1 for r+1 ≤ i ≤ r+s. For this it suffices to take n = 1 + ϕ(pe1+1 1 ···per+1 r p1 r+1 ···p1 r+s), because then 2n y + 1 ≡ 2y + 1 (mod pe1+1 1 ···per+1 r p1 r+1 ···p1 r+s). The last congruence means that pe1 1 ,...,per r divide exactly 2n y + 1 and no prime pr+1,...,pr+s divides 2n y + 1. It follows that the prime factorization of 2n y + 1 consists of the prime powers pe1 1 ,...,per r and powers of primes ≡ 1 (mod 4). Because y is odd, we obtain 2n y + 1 ≡ pe1 1 ···per r ≡ 2y + 1 ≡ 3 (mod 4). This is a contradiction since n > 1, and so 2n y + 1 ≡ 1 (mod 4). Now we proceed to the problem. If p is a prime divisor of 2n y + 1 the problem statement implies that xd ≡ 1 (mod p) for d = 2n . By Fermat’s little theorem the same congruence holds for d = p − 1, so it must also hold for d = (2n ,p − 1). For p ≡ 3 (mod 4) we have (2n ,p − 1) = 2, therefore in this case x2 ≡ 1 (mod p). In summary, we proved that every prime p ≡ 3 (mod 4) that divides some number of the form 2n y + 1 also divides x2 − 1. This is possible only if x = 1, otherwise by the above x2 − 1 would be a positive integer with infinitely many prime factors. Comment. For each x and each odd prime p the maximal power of p dividing x2n − 1 for some n is bounded and hence the same must be true for the numbers 2ny + 1. We infer that p2 divides 2p−1 −1 for each prime divisor p of 2ny+1. However trying to reach a contradiction with this conclusion alone seems hopeless, since it is not even known if there are infinitely many primes p without this property.49