HMMT 二月 2011 · TEAM2 赛 · 第 6 题

HMMT February 2011 — TEAM2 Round — Problem 6

[ 10 ] Let n be a positive integer such that n > 2. Prove that ϕ ( n ) is even. n

解析

[ 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 ) = n 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 and n n n n n n − a are different since gcd( n, ) = > 1, meaning is not in A . Hence we may evenly pair up the n 2 2 2 elements of A that sum to n , so ϕ ( n ), the number of elements of A , must be even, as desired. n n n