HMMT 二月 2010 · 冲刺赛 · 第 29 题
HMMT February 2010 — Guts Round — Problem 29
题目详情
- [ 18 ] Compute the remainder when 30303 ∑ k k k =1 is divided by 101.
解析
- [ 18 ] Compute the remainder when 30303 ∑ k k k =1 is divided by 101. Answer: 29 The main idea is the following lemma: 2 ∑ n + p − p k Lemma. For any non-negative integer n and prime p , k ≡ 1 (mod p ) . k = n +1 b Proof. Note that a depends only on the value of a (mod p ) and the value of b (mod p − 1). Since p 4 2 and p − 1 are relatively prime, the Chinese Remainder Theorem implies that any p − p consecutive integers will take on each possible pair of a residue mod p and a residue mod p − 1. In other words, if 2 we let ( a, b ) = ( k (mod p ) , k (mod p − 1)), then as k ranges through p − p consecutive integers, ( a, b ) 2 will range through all p − p ordered pairs of residues mod p and residues mod p − 1. This implies that 2 n + p − p p − 1 p ∑ ∑ ∑ k b k ≡ a . a =1 k = n +1 b =1 { ∑ − 1 p − 1 | b p b It is well-known that a = . We will sketch a proof here. When p − 1 | b , the a =1 0 p − 1 - b 5 result follows from Fermat’s Little Theorem . When p − 1 - b , it suffices to consider the case when b | p − 1, since the b th powers mod p are the same as the gcd( b, p − 1)th powers mod p , and there are an equal number of every non-zero b th power. But in this case, the b th powers are just the solutions p − 1 b to x − 1, which add up to zero by Vieta’s formulas. ∑ b Now, using the formula for a , we get that p − 1 p ∑ ∑ b a ≡ − 1 (mod p ) , a =1 b =1 which completes the lemma. ∑ 30303 k We now apply the lemma with p = 101 and n = 3, 10103, and 20103 to get that k ≡ k =1 ( ) ∑ ∑ 3 3 k k 1 2 3 k − 3. But k = 1 + 2 + 3 = 1 + 4 + 27 = 32, so the answer is 32 − 3 = 29. k =1 k =1