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 integern such that p divides n − q .2
解析
英文解析
- [55] Let p > 5 be a prime number. Show that there exists a prime number q < p and a positive integern such that p divides n − q .2
Proposed by: Andrew Gu
Solution 1: Note that the condition p | n − q just means that q is a quadratic residue modulo p , or 2
( )
that the Legendre symbol is 1. We use these standard facts about the Legendre symbol:qp
( )
• If p ≡ ± 1 (mod 8), then = 1.2
• For an odd prime p ,p
{
( ) − 1 − 1 if p ≡ 3 (mod 4) = .
+1 if p ≡ 1 (mod 4)p
• 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, sincep > 5. In that case q = 2 works. Otherwise assume p is not a Fermat prime or Mersenne prime, sothat 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 preciprocity = = 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 asthe 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
( ) ( ) ( )
q p a 2 = = = 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 wereproven:
√
• 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 ) = .
The proofs of the second and third results require knowledge of binary quadratic forms.4