Maths Olympiad Prep

Library / /592 of 740

, 2019

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:

For a given positive integer nn, we define φ(n)\varphi(n) to be the number of positive integers less than or equal to nn which share no common prime factors with nn. Find all positive integers nn for which
φ(2019n)=φ(n2) \varphi(2019 n)=\varphi\left(n^{2}\right)

Solution

Solution:

Let p1,p2,,pkp_{1}, p_{2}, \ldots, p_{k} be the prime divisors of nn. Then it is known that φ(n)=np11p1pk1pk\varphi(n)=n \cdot \frac{p_{1}-1}{p_{1}} \ldots \frac{p_{k}-1}{p_{k}}. As n2n^{2} and nn have the same set of prime divisors, it also holds that φ(n2)=n2p11p1pk1pk\varphi\left(n^{2}\right)=n^{2} \cdot \frac{p_{1}-1}{p_{1}} \ldots \frac{p_{k}-1}{p_{k}}. We will examine the equality in four cases.

- gcd(n,2019)=1\operatorname{gcd}(n, 2019)=1 In this case, 2019n2019 \cdot n has also 33 and 673673 as prime divisors, thus φ(2019n)=2019np11p1pk1pk23672673\varphi(2019 \cdot n)=2019 \cdot n \cdot \frac{p_{1}-1}{p_{1}} \ldots \frac{p_{k}-1}{p_{k}} \cdot \frac{2}{3} \cdot \frac{672}{673}, and the equality implies n=1342n=1342, however gcd(1342,3)1\operatorname{gcd}(1342,3) \neq 1, contradiction. Thus, there is no answer in this case.

- gcd(n,2019)=3\operatorname{gcd}(n, 2019)=3 In this case, 2019n2019 \cdot n has also 673673 as a prime divisor, thus φ(2019n)=2019np11p1pk1pk672673\varphi(2019 \cdot n)=2019 \cdot n \cdot \frac{p_{1}-1}{p_{1}} \ldots \frac{p_{k}-1}{p_{k}} \cdot \frac{672}{673}, and the equality implies n=2016n=2016, which satisfies the equation. Thus, the only answer in this case is n=2016n=2016.

- gcd(n,2019)=673\operatorname{gcd}(n, 2019)=673 In this case, 2019n2019 \cdot n has also 33 as a prime divisor, thus φ(2019n)=2019np11p1pk1pk23\varphi(2019 \cdot n)=2019 \cdot n \cdot \frac{p_{1}-1}{p_{1}} \ldots \frac{p_{k}-1}{p_{k}} \cdot \frac{2}{3}, and the equality implies n=1346n=1346, which satisfies the equation. Thus, the only answer in this case is n=1346n=1346.

- gcd(n,2019)=2019\operatorname{gcd}(n, 2019)=2019 In this case, 2019n2019 \cdot n has the same set of prime divisors, thus φ(2019n)=2019np11p1pk1pk\varphi(2019 \cdot n)=2019 \cdot n \cdot \frac{p_{1}-1}{p_{1}} \ldots \frac{p_{k}-1}{p_{k}}, and the equality implies n=2019n=2019, which satisfies the equation. Thus, the only answer in this case is n=2019n=2019.

Thus, all the answers are n=1346,2016,2019n=1346, 2016, 2019.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.