HMMT 二月 2011 · TEAM1 赛 · 第 3 题

HMMT February 2011 — TEAM1 Round — Problem 3

[ 15 ] Let n be a positive integer, and let a , a , . . . , a be a set of positive integers such that a = 2 and 1 2 n 1 a = ϕ ( a ) for all 1 ≤ m ≤ n − 1, where, for all positive integers k , ϕ ( k ) denotes the number of m m +1 n − 1 positive integers less than or equal to k that are relatively prime to k . Prove that a ≥ 2 . n Complex Numbers [35]

解析

[ 15 ] Let n be a positive integer, and let a , a , . . . , a be a set of positive integers such that a = 2 and 1 2 n 1 a = ϕ ( a ) for all 1 ≤ m ≤ n − 1, where, for all positive integers k , ϕ ( k ) denotes the number of m m +1 n − 1 positive integers less than or equal to k that are relatively prime to k . Prove that a ≥ 2 . n Solution: We first note that ϕ ( s ) < s for all positive integers s ≥ 2, so a > 2 for all m > 1. m For integers s > 2, let A be the set of all positive integers x ≤ s such that gcd( s, x ) = 1. Since s gcd( s, x ) = gcd( s, s − x ) for all x , if a is a positive integer in A , so is s − a . Moreover, if a is in A , s s s s s a and s − a are different since gcd( s, ) = > 1, meaning is not in A . Hence we may evenly pair s 2 2 2 Team Round A up the elements of A that sum to s , so ϕ ( s ), the number of elements of A , must be even. It follows s s that a is even for all m ≤ n − 1. m t If t > 2 is even, A will not contain any even number, so ϕ ( t ) ≤ . We may conclude that a ≥ 2 a t m m − 1 2 n − 2 n − 1 for all m ≤ n − 1, so a ≥ a ≥ 2 a = 2 , as desired. n n − 1 1 i Finally, note that such a set exists for all n by letting a = 2 for all i . i Complex Numbers [35]