HMMT 二月 2016 · 冲刺赛 · 第 11 题

英文解析

11. [ 7 ] Define φ ( n ) as the product of all positive integers less than or equal to n and relatively prime ton . Compute the remainder when
    ∑
    !
    φ ( n )
    2 ≤ n ≤ 50
    gcd( n, 50)=1
    is divided by 50.
    Proposed by: Evan Chen
    Answer: 12
    !
    First, φ ( n ) is even for all odd n , so it vanishes modulo 2.
    ! ! !
    To compute the remainder modulo 25, we first evaluate φ (3) + φ (7) + φ (9) ≡ 2 + 5 · 4 + 5 · 3 ≡ 12
    (mod 25). Now, for n ≥ 11 the contribution modulo 25 vanishes as long as 5 - n .
    We conclude the answer is 12.