PUMaC 2015 · 数论（A 组） · 第 8 题
PUMaC 2015 — Number Theory (Division A) — Problem 8
题目详情
- [ 8 ] Let n = 2 − 1. For any integer 1 ≤ x < n , let ∑ f ( x ) = s ( n − x ) + s ( x ) − s ( n ) , n p p p p where s ( k ) denotes the sum of the digits of k when written in base q and the summation q is over all primes p . Let N be the number of values of x such that 4 | f ( x ). What is the n remainder when N is divided by 1000? 1
解析
- [ 8 ] Let n = 2 − 1. For any integer 1 ≤ x < n , let ∑ f ( x ) = s ( n − x ) + s ( x ) − s ( n ) , n p p p p where s ( k ) denotes the sum of the digits of k when written in base q and the summation q is over all primes p . Let N be the number of values of x such that 4 | f ( x ). What is the n remainder when N is divided by 1000? Solution: First, observe that for any integer k and prime p , the number of times p divides k ! is: k − s ( k ) p v ( k !) = p p − 1 Then, we find that: (( )) ( ) n n ! v = v p p x x !( n − x )! ( ) ( ) ( ) n − s ( n ) − x − s ( x ) − ( n − x ) − s ( n − x ) p p p = p − 1 (( )) n ( p − 1) v = s ( n − x ) + s ( x ) − s ( n ) p p p p x ( ) n 2015 Now, since n = 2 − 1, it is clear that 2 - for any x , so in any non-zero term in the x summation, p − 1 is always even. Let P be the set of primes p ≡ i ( mod 4). We then have that i 4 | p − 1 when p ∈ P , so we only need to worry about the primes p ∈ P . 1 3 Now, taking the summation of each p ∈ P term modulo 4, the problem is reduced to proving 3 that: ∣ (( )) ∣ ∑ n ∣ 2 v ∣ p ∣ x p ∈P 3 Now, note that the product of an even number of primes p ∈ P is equivalent to 1( mod 4) and 3 an odd number 3(mod4). Thus, the above statement is equivalent to: ( ) n ≡ 1(mod4) x 4 n For x < , we have: 2 x ∏ n − i + 1 x ≡ ( − 1) (mod4) i i =1 x 1 ≡ ( − 1) (mod4) ⌊ ⌋ n b c 2 2013 n Which means that x is even, so there are = 2 − 1 values of x < that satisfy the 2 2 ( ) n n condition. Since is symmetric about , the total number of x that satisfy the condition is x 2 2014 2 − 2. n φ (125) 100 Note that 2 ≡ 0 (mod 8) for n ≥ 3 and that, by the Euler-Fermat Theorem, 2 = 2 ≡ 1 2014 14 (mod 125). From this we conclude that 2 − 2 ≡ 2 − 2 ≡ 16384 − 2 ≡ 382 (mod 1000). Author: Bill Huang 5