IMO 2012 Shortlist N8

Category: Number Theory

Problem

Prove that for every prime p > 100 and every integer r there exist two integers a and b such that p divides a2

• b5 − r. Solution 1. Throughout the solution, all congruence relations are meant modulo p. Fix p, and let P = {0,1,...,p−1} be the set of residue classes modulo p. For every r ∈ P, let Sr =  (a,b) ∈ P × P: a2
• b5 ≡ r , and let sr = |Sr|. Our aim is to prove sr > 0 for all r ∈ P. We will use the well-known fact that for every residue class r ∈ P and every positive integer k, there are at most k values x ∈ P such that xk ≡ r. Lemma. Let N be the number of quadruples (a,b,c,d) ∈ P4 for which a2
• b5 ≡ c2
• d5 . Then N = X r∈P s2 r (a) and N ≤ p(p2
• 4p − 4). (b) Proof. (a) For each residue class r there exist exactly sr pairs (a,b) with a2
• b5 ≡ r and sr pairs (c,d) with c2 +d5 ≡ r. So there are s2 r quadruples with a2 +b5 ≡ c2 +d5 ≡ r. Taking the sum over all r ∈ P, the statement follows. (b) Choose an arbitrary pair (b,d) ∈ P and look for the possible values of a,c.

1. Suppose that b5 ≡ d5 , and let k be the number of such pairs (b,d). The value b can be chosen in p different ways. For b ≡ 0 only d = 0 has this property; for the nonzero values of b there are at most 5 possible values for d. So we have k ≤ 1 + 5(p − 1) = 5p − 4. The values a and c must satisfy a2 ≡ c2 , so a ≡ ±c, and there are exactly 2p − 1 such pairs (a,c).
2. Now suppose b5 6≡ d5 . In this case a and c must be distinct. By (a−c)(a+c) = d5 −b5 , the value of a − c uniquely determines a + c and thus a and c as well. Hence, there are p − 1 suitable pairs (a,c). Thus, for each of the k pairs (b,d) with b5 ≡ d5 there are 2p−1 pairs (a,c), and for each of the other p2 − k pairs (b,d) there are p − 1 pairs (a,c). Hence, N = k(2p−1)+(p2 −k)(p−1) = p2 (p−1)+ kp ≤ p2 (p−1)+(5p−4)p = p(p2 +4p−4).  To prove the statement of the problem, suppose that Sr = ∅ for some r ∈ P; obviously r 6≡ 0. Let T =  x10 : x ∈ P \ {0} be the set of nonzero 10th powers modulo p. Since each residue class is the 10th power of at most 10 elements in P, we have |T| ≥ p−1 ≥ 4 by p > 100. For every t ∈ T, we have Str = ∅. Indeed, if (x,y) ∈ Str and t ≡ z10 then (z−5 x)2

• (z−2 y)5 ≡ t−1 (x2
• y5 ) ≡ r, so (z−5 x,z−2 y) ∈ Sr. So, there are at least p−1 ≥ 4 empty sets among S1,...,Sp−1, and there are at most p − 4 nonzero values among s0,s2,...,sp−1. Then by the AM-QM inequality we obtain N = X r∈P\rT s2 r ≥ p − 4   X r∈P\rT sr   = |P × P|2 p − 4 = p4 p − 4

p(p2

• 4p − 4), which is impossible by the lemma.51 Solution 2. If 5 ∤ p − 1, then all modulo p residue classes are complete fifth powers and the statement is trivial. So assume that p = 10k + 1 where k ≥ 10. Let g be a primitive root modulo p. We will use the following facts: (F1) If some residue class x is not quadratic then x(p−1)/2 ≡ −1 (mod p). (F2) For every integer d, as a simple corollary of the summation formula for geometric pro- gressions, 2k−1 X i=0 g5di ≡ ( 2k if 2k d 0 if 2k 6 | d (mod p). Suppose that, contrary to the statement, some modulo p residue class r cannot be expressed as a2 +b5 . Of course r 6≡ 0 (mod p). By (F1) we have (r−b5 )(p−1)/2 = (r−b5 )5k ≡ −1 (mod p) for all residue classes b. For t = 1,2...,k − 1 consider the sums S(t) = 2k−1 X i=0 r − g5i
  5k g5ti . By the indirect assumption and (F2), S(t) = 2k−1 X i=0 r − (gi )5
  5k g5ti ≡ 2k−1 X i=0 (−1)g5ti ≡ − 2k−1 X i=0 g5ti ≡ 0 (mod p) because 2k cannot divide t. On the other hand, by the binomial theorem, S(t) = 2k−1 X i=0 5k X j=0  5k j  r5k−j − g5i
  j ! g5ti = 5k X j=0 (−1)j  5k j  r5k−j 2k−1 X i=0 g5(j+t)i ! ≡ ≡ 5k X j=0 (−1)j  5k j  r5k−j ( 2k if 2k j + t 0 if 2k 6 | j + t (mod p). Since 1 ≤ j + t < 6k, the number 2k divides j + t only for j = 2k − t and j = 4k − t. Hence, 0 ≡ S(t) ≡ (−1)t  5k 2k − t  r3k+t

 5k 4k − t  rk+t  · 2k (mod p),  5k 2k − t  r2k +  5k 4k − t  ≡ 0 (mod p). Taking this for t = 1,2 and eliminating r, we get 0 ≡  5k 2k − 2  5k 2k − 1  r2k +  5k 4k − 1  −  5k 2k − 1  5k 2k − 2  r2k +  5k 4k − 2 

 5k 2k − 2  5k 4k − 1  −  5k 2k − 1  5k 4k − 2 

(5k)!2 (2k − 1)!(3k + 2)!(4k − 1)!(k + 2)!  (2k − 1)(k + 2) − (3k + 2)(4k − 1) 

−(5k)!2 · 2k(5k + 1) (2k − 1)!(3k + 2)!(4k − 1)!(k + 2)! (mod p). But in the last expression none of the numbers is divisible by p = 10k + 1, a contradiction.52 Comment 1. The argument in the second solution is valid whenever k ≥ 3, that is for all primes p = 10k + 1 except p = 11. This is an exceptional case when the statement is not true; r = 7 cannot be expressed as desired. Comment 2. The statement is true in a more general setting: for every positive integer n, for all sufficiently large p, each residue class modulo p can be expressed as a2 + bn. Choosing t = 3 would allow using the Cauchy-Davenport theorem (together with some analysis on the case of equality). In the literature more general results are known. For instance, the statement easily follows from the Hasse-Weil bound.