HMMT 十一月 2019 · 冲刺赛 · 第 27 题
HMMT November 2019 — Guts Round — Problem 27
题目详情
- [13] For a given positive integer n , we define ϕ ( n ) to be the number of positive integers less than or equal to n which share no common prime factors with n . Find all positive integers n for which 2 ϕ (2019 n ) = ϕ ( n ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2019, November 9, 2019 — GUTS ROUND Organization Team Team ID#
解析
- [13] For a given positive integer n , we define ϕ ( n ) to be the number of positive integers less than or equal to n which share no common prime factors with n . Find all positive integers n for which 2 ϕ (2019 n ) = ϕ ( n ) . Proposed by: Carl Schildkraut Answer: 1346 , 2016 , 2019 p − 1 p − 1 1 k 2 Let p , p , . . . , p be the prime divisors of n . Then it is known that ϕ ( n ) = n · . . . . As n and 1 2 k p p 1 k p − 1 p − 1 2 2 1 k n has the same set of prime divisors, it also holds that ϕ ( n ) = n · . . . . We will examine the p p 1 k equality in four cases. • gcd( n, 2019) = 1 In this case, 2019 · n has also 3 and 673 as prime divisors, thus ϕ (2019 · n ) = p − 1 p − 1 2 672 1 k 2019 · n · . . . · · , and the equality implies n = 1342, however gcd(1342 , 3) 6 = 1, p p 3 673 1 k contradiction. Thus, there is no answer in this case. • gcd( n, 2019) = 3 In this case, 2019 · n has also 673 as a prime divisor, thus ϕ (2019 · n ) = p − 1 p − 1 672 1 k 2019 · n · . . . · , and the equality implies n = 2016, which satisfies the equation. Thus, p p 673 1 k the only answer in this case is n = 2016. • gcd( n, 2019) = 673 In this case, 2019 · n has also 3 as a prime divisor, thus ϕ (2019 · n ) = p − 1 p − 1 2 1 k 2019 · n · . . . · , and the equality implies n = 1346, which satisfies the equation. Thus, p p 3 1 k the only answer in this case is n = 1346. • gcd( n, 2019) = 2019 In this case, 2019 · n has the same set of prime divisors, thus ϕ (2019 · n ) = p − 1 p − 1 1 k 2019 · n · . . . , and the equality implies n = 2019, which satisfies the equation. Thus, the p p 1 k only answer in this case is n = 2019. Thus, all the answers are n = 1346 , 2016 , 2019.