HMMT 二月 2010 · 冲刺赛 · 第 29 题

英文解析

29. [ 18 ] Compute the remainder when
    30303
    ∑
    k =1 kkis divided by 101.
    Answer: 29 The main idea is the following lemma:
    ∑2
    n + p − pk
    Lemma. For any non-negative integer n and prime p , k ≡ 1 (mod p ) .
    k = n +1
    Proof. Note that a depends only on the value of a (mod p ) and the value of b (mod p − 1). Since pb
    4 2
    and p − 1 are relatively prime, the Chinese Remainder Theorem implies that any p − p consecutiveintegers will take on each possible pair of a residue mod p and a residue mod p − 1. In other words, ifwe 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 2
    ∑ ∑ ∑
    k bk ≡ a .
    a =1
    k = n +1 b =1
    {
    ∑
    − 1 p − 1 | bp
    It is well-known that a = . We will sketch a proof here. When p − 1 | b , theba =1
    0 p − 1 - bresult follows from Fermat’s Little Theorem . When p − 1 - b , it suffices to consider the case when 5
    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 arean equal number of every non-zero b th power. But in this case, the b th powers are just the solutionsp − 1
    to x − 1, which add up to zero by Vieta’s formulas.b
    ∑
    Now, using the formula for a , we get thatbp − 1 p
    ∑ ∑
    a ≡ − 1 (mod p ) ,ba =1
    b =1
    which completes the lemma.
    ∑
    30303
    We now apply the lemma with p = 101 and n = 3, 10103, and 20103 to get that k ≡kk =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