PUMaC 2015 · 数论（B 组） · 第 8 题
PUMaC 2015 — Number Theory (Division B) — Problem 8
题目详情
- [ 8 ] Given a positive integer k , let f ( k ) be the sum of the k -th powers of the primitive roots of
- For how many positive integers k < 2015 is f ( k ) divisible by 73? Note: A primitive root r of a prime p is an integer 1 ≤ r < p such that the smallest positive k integer k such that r ≡ 1 (mod p ) is k = p − 1 . 1
解析
- [ 8 ] Given a positive integer k , let f ( k ) be the sum of the k -th powers of the primitive roots of
- For how many positive integers k < 2015 is f ( k ) divisible by 73? Note: A primitive root r of a prime p is an integer 1 ≤ r < p such that the smallest positive k integer k such that r ≡ 1 (mod p ) is k = p − 1 . Solution: k Denote S to be the sum of the k -th powers of the residues of order d modulo p = 73. Now, d for any primitive root r of p , we have: ord ( r ) p − 1 p k ord ( r ) = = = d p k gcd( k, p − 1) gcd( k, p − 1) 2 Furthermore, the number of residues of p of order d is: n = φ ( d ) d k Now, since d is independent of the primitive root r , S is equal to a sum of n residues of k p − 1 1 order d . More specifically, due to symmetry within the group Z /p Z , each residue or order d k k is represented in the sum the same number of times. Then, we have: ( ) n φ ( p − 1) p − 1 k S = · S = ( ) · S = φ gcd( k, p − 1) · S d d d 1 k k k p − 1 n φ d k gcd( k,p − 1) ( ) Clearly, p - φ gcd( k, p − 1) < p , so p | S . We now present a lemma: d k Lemma 1: For some d | p − 1, S ≡ 0 (mod p ) iff d is divisible by a perfect square. Furthermore, d m if d = q q . . . q is square-free, then we have that S ≡ ( − 1) . 1 2 m d 0 Proof: We prove by induction. For d = 1, it is clear that S = 1 = ( − 1) . Now, assume this is 1 ′ d − 1 d − 2 true for all d < d . Let x be a residue of order d modulo p . Clearly, p | x + x + . . . + x +1, d as p | x − 1 by assumption and p - x − 1. But, we have: ∑ d − 1 d − 2 ′ x + x + . . . + x + 1 = S ≡ 0 (mod p ) d ′ d | d If d is square-free, we write d = q q . . . q . Then, we have: 1 2 m ( ) ( ) ( ( )) m − 1 ∑ ∑ m m i m m ′ S ≡ − S ≡ ( − 1) ( − 1) ≡ ( − 1) − ( − 1) ≡ ( − 1) (mod p ) d d i m ′ ′ i =0 d | d,d 6 = d α α 1 2 α m Otherwise, we write d = q q . . . q and e = q q . . . q < d . Then, we have: 1 2 m m 1 2 ( ) ( ) m ∑ ∑ ∑ m i ′ ′ S ≡ − S ≡ − S ≡ ( − 1) ( − 1) ≡ 0 (mod p ) d d e i ′ ′ ′ i =0 d | d,d 6 = d e | e As desired. This means that k satisfies the condition iff d is divisible by a perfect square. Since p − 1 = k 3 2 2 72 = 2 · 3 , d is square-free iff 2 · 3 = 12 | k , so k satisfies the condition iff 12 - k . There are k 2014 2014 − b c = 1847 such k . 12 Author: Bill Huang 3