PUMaC 2023 · 数论（A 组） · 第 8 题
PUMaC 2023 — Number Theory (Division A) — Problem 8
题目详情
- Let S = 0 , S = 1, and for n ≥ 2 let S = S + 5 S . What is the sum of the five smallest 0 1 n n − 1 n − 2 primes p such that p | S ? p − 1 Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 1
解析
- Let S = 0 , S = 1, and for n ≥ 2 let S = S + 5 S . What is the sum of the five smallest 0 1 n n − 1 n − 2 primes p such that p | S ? p − 1 Proposed by Owen Yang Answer: 185 √ √ n n 1 1+ 21 1 − 21 √ Claim 1: S = − n 2 2 21 Proof: We proceed by strong induction. Our base cases are S = 0 and S = 1 which can be 0 1 easily checked to work. For the inductive step, we have that ! √ 2 √ √ √ 1 + 21 22 + 2 21 11 + 21 1 + 21 = = = + 5 2 4 2 2 and similarly ! √ 2 √ √ √ 1 − 21 22 − 2 21 11 − 21 1 − 21 = = = + 5 2 4 2 2 so if the formulas work for S and S then we have n − 1 n ! ! √ n √ n − 1 1 1 + 21 1 + 21 S = S + 5 S = √ + 5 n +1 n n − 1 2 2 21 ! ! √ n √ n − 1 1 − 21 1 − 21 − − 5 2 2 ! ! ! √ n √ n 1 1 + 21 1 − 21 √ = − 2 2 21 as desired. Claim 2: n − 1 P ⌊ ⌋ n 2 k 21 k =0 2 k +1 S = n n − 1 2 Proof: We compute the coefficients in the binomial expansions of the formula from Claim 1. We have ! √ √ P P i n n n n i 21 − ( − 21) 1 i =0 i =0 i i √ S = n n 2 21 5 for which the coefficients cancel when i is even and are doubled when i is odd. Re-indexing with i = 2 k + 1, we find that n − 1 n − 1 √ P P ⌊ ⌋ ⌊ ⌋ n n 2 2 k k 2 21 21 21 1 k =0 k =0 2 k +1 2 k +1 √ S = = n n n − 1 2 2 21 as desired. p − 1 p − 1 − 1 2 2 Claim 3: For prime p ̸ = 2, we have that S ≡ 21 mod p and S ≡ 2 (1+21 ) mod p . p p +1 n Proof: Note that since p is prime, p divides all binomial coefficients with n = p except k for k = 0 and k = p . Then since the sum formula from Claim 2 contains only coefficients with p k odd, the only one not divisible by p is the last one, = 1 (here we use the fact that p is p odd). Then we find that p − 1 ⌊ ⌋ 2 X p − 1 p p − 1 k 2 2 S = 21 ≡ 21 (mod p ) p 2 k + 1 k =0 p − 1 p − 1 2 and since 2 ≡ 1 (mod p ) by Fermat’s Little Theorem, we obtain that S ≡ 21 (mod p ) p as desired. Similarly, for n = p + 1 we know that p divides all coefficients between k = 2 and p − 1, inclusive. The odd values of k are 1 and p , so p ⌊ ⌋ 2 X p − 1 p + 1 p + 1 p + 1 p k 0 2 2 S = 21 ≡ 21 + 21 (mod p ) p +1 2 k + 1 1 p k =0 p − 1 p − 1 2 2 ≡ ( p + 1)(1 + 21 ) (mod p ) ≡ 1 + 21 (mod p ) so that p − 1 p 2 2 S ≡ 2 S ≡ 1 + 21 (mod p ) p +1 p +1 p − 1 − 1 2 = ⇒ S ≡ 2 (1 + 21 ) (mod p ) p +1 21 Claim 4: For prime p ̸ = 2 , 3 , 5 , 7, p | S ⇐⇒ = 1. p − 1 p − 1 Proof: First note that S ≡ S + 5 S (mod p ) = ⇒ S ≡ 5 ( S − S ). Now p +1 p p − 1 p − 1 p +1 p p − 1 21 2 if = 1 then 21 ≡ 1 (mod p ) and from Claim 3 we calculate that S ≡ S ≡ 1 p p +1 p − 1 (mod p ). Then S ≡ 5 ( S − S ) ≡ 0 (mod p ) as desired. For the inverse, since p ∤ 21 we p − 1 p +1 p p − 1 21 2 have = − 1, so that 21 ≡ − 1 (mod p ). In particular, S ≡ − 1 (mod p ) and S ≡ 0 p p +1 p − 1 (mod p ), so S ≡ 5 ̸ ≡ 0 (mod p ). p − 1 Now we can explicitly check the edge cases: we have 2 ∤ S = 1, 3 ∤ S = 1, 5 ∤ S = 11, 1 2 4 21 and 7 ∤ S = 86. Therefore, we just need to find the smallest five primes such that = 1. 6 p ( p − 1) p p p p 21 3 7 (1+3) 2 By quadratic reciprocity, we have that = = ( − 1) = . p p p 3 7 3 7 Then p must be either a residue or non-residue in both moduli, i.e. both p ≡ 1 (mod 3) and p ≡ 1 , 2, or 4 (mod 7), or both p ≡ 2 (mod 3) and p ≡ 3 , 5, or 6 (mod 7). The smallest five primes with this property are 17 , 37 , 41 , 43, and 47, so our final answer is 17+37+41+43+47 = 185 . 6