PUMaC 2019 · 数论（A 组） · 第 7 题
PUMaC 2019 — Number Theory (Division A) — Problem 7
题目详情
- Let f ( x ) be the nonnegative remainder when x is divided by the prime p = 1297. Let g ( x ) be the largest possible value of f ( − p ) + f ( − p ) + . . . + f ( − p ) over all sets { p , . . . , p } where 1 2 m 1 m 2 2 p are primes such that for all 1 ≤ i < j ≤ m we have p - ( p − p ), and k i j x − 1 p - σ (( p × . . . × p ) ) , 1 m where σ ( x ) is the sum of the (distinct, positive, not necessarily proper) divisors of x . Find ( p +1) / 2 ∑ ( g ( p − 2 k + 3) − g ( p + 2 k + 1)) . k =1 − 1
解析
- Let f ( x ) be the nonnegative remainder when x is divided by the prime p = 1297. Let g ( x ) be the largest possible value of f ( − p ) + f ( − p ) + . . . + f ( − p ) over all sets { p , . . . , p } where 1 2 m 1 m 2 2 p are primes such that for all 1 ≤ i < j ≤ m we have p - ( p − p ), and k i j x − 1 p - σ (( p × . . . × p ) ) , 1 m where σ ( x ) is the sum of the (distinct, positive, not necessarily proper) divisors of x . Find ( p +1) / 2 ∑ ( g ( p − 2 k + 3) − g ( p + 2 k + 1)) . k =1 Proposed by: Michael Gintz Answer: 2557 By dirichlet’s theorem, we can find a prime with any value mod p . Now note that σ is the x product of ( p − 1) / ( p − 1). If p is 1 mod p , then the value it multiplies is not 0 mod p unless k k k x is 0 mod p. Thus we have values 1 mod p here except in g (2 p ). Thus for 2 to p − 1 we can x simply consider whether p is 1 mod p, and then take the max of p and p − p . Define h as k k k g but the p cannot be 1 mod p. k Note for that we can arbitrarily choose some primitive root r , write every number from 2 to k p − 2 as r , and then to see whether we can include f ( r ) in g ( x ) we simply see if ( p − 1) - xk . Then we have that h ( x ) = h ( x + p − 1) and h ( x ) = h ( p − 1 − x ), and thus we are looking for h (2) + . . . + h ( p + 1) − h ( p + 3) − . . . − h (2 p + 2) + ( p − 1) = 2 h ( p + 1) − h (2 p ) − h (2 p + 2) + ( p − 1) = h (2) − h (4) + ( p − 1) where the ( p − 1) comes from the fact that g (2 p ) cannot include p ≡ ± 1 (mod p ). Note that k h (2) can include everything whose square is not 1 mod p, which is everything from ( p + 1) / 2 to p − 2. Then note that h (4) contains everything whose 4th power is not 1 mod p. Note that 4 1296 = 6 , so 36 is a 4th root. Thus this is everything from ( p + 1) / 2 to p − 2 except p − 36. Thus h (2) − h (4) = ( p − 36) and our answer is 2 p − 37 = 2557. − 1