返回题库

HMMT 二月 2020 · 冲刺赛 · 第 34 题

HMMT February 2020 — Guts Round — Problem 34

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

题目详情

英文原题

  1. [22] For odd primes p , let f ( p ) denote the smallest positive integer a for which there does not exist an
    2 2 5
    integer n satisfying p | n − a . Estimate N , the sum of f ( p ) over the first 10 odd primes p .
    An estimate of E > 0 will receive b 22 min( N/E, E/N ) c points.3
解析

英文解析

  1. [22] For odd primes p , let f ( p ) denote the smallest positive integer a for which there does not exist an
    2 2 5
    integer n satisfying p | n − a . Estimate N , the sum of f ( p ) over the first 10 odd primes p .
    An estimate of E > 0 will receive b 22 min( N/E, E/N ) c points.3
    Proposed by: Michael Ren
    Answer: 2266067
    Solution: Note that the smallest quadratic nonresidue a is always a prime, because if a = bc withb, c > 1 then one of b and c is also a quadratic nonresidue. We apply the following heuristic: if p ,
    p , . . . are the primes in increasing order, then given a “uniform random prime” q , the values of 1
    ( ) ( )2
    p p
    1 1
    1 2
    , , . . . are independent and are 1 with probability and − 1 with probability .
    q q 2 2
    Of course, there is no such thing as a uniform random prime. More rigorously, for any n , the joint dis-
    ( ) ( )
    p p
    1 ntributions of , . . . , where q is a uniform random prime less than N converges in distributionq qto n independent coin flips between 1 and − 1 as N → ∞ . For ease of explanation, we won’t adoptthis more formal view, but it is possible to make the following argument rigorous by looking at primesq < N and sending N → ∞ . Given any n , the residue of q mod n is uniform over the ϕ ( n ) residuesmod n that are relatively prime to n . By quadratic reciprocity, conditioned on either q ≡ 1 (mod 4) or
    ( )
    q ≡ 3 (mod 4), exactly half of the nonzero residues mod p satisfy = 1 and exactly half satisfynpn
    ( )qp = − 1 for odd p (the case of p = 2 is slightly different and one must look mod 8, but the resultnn nis the same). The residue of q mod 8, p , p , . . . , p are independent as these are pairwise relativelyq
    2 3 nprime, yielding our heuristic.
    Thus, we may model our problem of finding the smallest quadratic nonresidue with the followingprocess: independent fair coins are flipped for each prime, and we take the smallest prime that flipped
    ∑2
    ∞ pn 2
    heads. We can estimate the expected value of f ( p ) as . Looking at the first few terms givesnn =1
    us 2
    2 2 2 2 2 2 2 2 2 2
    2 3 5 7 11 13 17 19 23 29 + + + + + + + + + ≈ 22 .
    2 4 8 16 32 64 128 256 512 1024
    The terms after this decay rapidly, so a good approximation is E = 22 · 10 , good enough for 20 points.5
    The more inaccurate E = 20 · 10 earns 15 points.5
    This Python code computes the exact answer:
    def smallest_nqr(p):
    for a in range(1,p):
    if pow(a,(p-1)//2,p)==p-1:
    return aimport sympyprint(sum([smallest_nqr(p)2 for p in sympy.ntheory.primerange(3,sympy.prime(105+2))]))
    Remark. In 1961, Erd˝ os showed that as N → ∞ , the average value of f ( p ) over odd primes p < N
    ∑
    ∞
    will converge to ≈ 3 . 675.npnn =1 2