返回题库

HMMT 十一月 2019 · 冲刺赛 · 第 27 题

HMMT November 2019 — Guts Round — Problem 27

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

  1. [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#

解析

英文解析

  1. [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.