HMMT 二月 2011 · TEAM2 赛 · 第 6 题

英文解析

6. [ 10 ] Let n be a positive integer such that n > 2. Prove that ϕ ( n ) is even.
   Solution: Let A be the set of all positive integers x ≤ n such that gcd( n, x ) = 1. Since gcd( n, x ) =
   gcd( n, n − x ) for all x , if a is a positive integer in A , so is n − a . Moreover, if a is in A , a andnn nn n nn − a are different since gcd( n, ) = > 1, meaning is not in A . Hence we may evenly pair up the
   2 2 2 nelements of A that sum to n , so ϕ ( n ), the number of elements of A , must be even, as desired.
   n nn