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 equalto n which share no common prime factors with n . Find all positive integers n for whichϕ (2019 n ) = ϕ ( n ) .2
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
ϕ (2019 n ) = ϕ ( n 2 ) .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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 orequal to n which share no common prime factors with n . Find all positive integers n for whichϕ (2019 n ) = ϕ ( n ) .2
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 kp p
1 kp − 1 p − 1
2 2 1
n has the same set of prime divisors, it also holds that ϕ ( n ) = n · . . . . We will examine thekp p
1 kequality 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 kcontradiction. 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
1 k 672
2019 · n · . . . · , and the equality implies n = 2016, which satisfies the equation. Thus,
p p 673
k 1
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
1 k 2
2019 · n · . . . · , and the equality implies n = 1346, which satisfies the equation. Thus,
p p 3
1 kthe 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, thep p
1 konly answer in this case is n = 2019.
Thus, all the answers are n = 1346 , 2016 , 2019.