返回题库

HMMT 二月 2020 · 团队赛 · 第 9 题

HMMT February 2020 — Team Round — Problem 9

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [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
解析

英文解析

  1. [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