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

HMMT February 2016 — Guts Round — Problem 11

[ 7 ] Define φ ( n ) as the product of all positive integers less than or equal to n and relatively prime to n . Compute the remainder when ∑ ! φ ( n ) 2 ≤ n ≤ 50 gcd( n, 50)=1 is divided by 50.

解析

[ 7 ] Define φ ( n ) as the product of all positive integers less than or equal to n and relatively prime to n . 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.