HMMT 二月 2020 · 团队赛 · 第 9 题
HMMT February 2020 — Team Round — Problem 9
题目详情
- [55] Let p > 5 be a prime number. Show that there exists a prime number q < p and a positive integer 2 n such that p divides n − q .
解析
- [55] Let p > 5 be a prime number. Show that there exists a prime number q < p and a positive integer 2 n such that p divides n − q . Proposed by: Andrew Gu 2 Solution 1: Note that the condition p | n − q just means that q is a quadratic residue modulo p , or ( ) q that the Legendre symbol is 1. We use these standard facts about the Legendre symbol: p ( ) 2 • If p ≡ ± 1 (mod 8), then = 1. p • For an odd prime p , { ( ) − 1 − 1 if p ≡ 3 (mod 4) = . p +1 if p ≡ 1 (mod 4) • Quadratic reciprocity: for distinct odd primes p and q , { ( ) ( ) p q − 1 if p ≡ q ≡ 3 (mod 4) = . q p +1 otherwise If p is a Fermat prime or Mersenne prime, then p is congruent to 1 or 7 modulo 8 respectively, since p > 5. In that case q = 2 works. Otherwise assume p is not a Fermat prime or Mersenne prime, so that p − 1 and p + 1 are not powers of 2. If p ≡ 1 (mod 4), then let q be an odd prime divisor of p − 1, so that p ≡ 1 (mod q ). Then by quadratic ( ) ( ) q p reciprocity = = 1. p q If p ≡ 3 (mod 4), then let q be an odd prime divisor of p + 1, so that p ≡ − 1 (mod q ). Either q ≡ 1 ( ) ( ) ( ) ( ) ( ) q p q p − 1 (mod 4) so that = = 1 or q ≡ 3 (mod 4) so that = − = − = 1. p q p q q Solution 2: (Ankan Bhattacharya) We assume the same standard facts about quadratic residues as the previous solution. If p ≡ 1 (mod 4), then since p > 5, there exists an odd prime divisor q of p − 4, which gives ( ) ( ) ( ) q p 4 = = = 1 . p q q If p ≡ 7 (mod 8), then we can take q = 2. If p ≡ 3 (mod 8), then by Legendre’s three square theorem there exist odd a, b, c satisfying p = 2 2 2 a + b + c . Since p > 3, these are not all equal and we may assume without loss of generality that 2 2 2 b 6 = c . Then p − a = b + c has a prime divisor q ≡ 1 (mod 4), which gives ( ) ( ) ( ) 2 q p a = = = 1 . p q q Remark. For an odd prime number p , let l ( p ) be the least prime number which is a quadratic residue √ modulo p and h ( − p ) be the class number of the quadratic field Q [ − p ]. In the paper “The Least Prime Quadratic Residue and the Class Number” by Chowla, Cowles, and Cowles, the following results were proven: √ • If p > 5 and p ≡ 5 (mod 8), then l ( p ) < p . √ • If p > 3, p ≡ 3 (mod 8), and h ( − p ) > 1, then l ( p ) < p/ 3. p +1 • If p > 3, p ≡ 3 (mod 8), and h ( − p ) = 1, then l ( p ) = . 4 The proofs of the second and third results require knowledge of binary quadratic forms.