HMMT 二月 2020 · 冲刺赛 · 第 34 题
HMMT February 2020 — Guts Round — Problem 34
题目详情
英文原题
- [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
解析
英文解析
- [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