$n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021))$

Question

VMO 2021:

Find all integers $n \geq 2$ such that: $n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021))$

I think $n$ does not exsist.

+, If $\gcd(n,2021)=1 \Rightarrow \gcd(n+2021,n)=1$

then $(n+2021) \mid (n+1- \phi(n))$

What should I do next?

Answer 1

There are some brute force approach is involved in my solution. Given that this is an Olympiad question, there should be a way to avoid the brute force approach. The main idea of the solution comes from the comment https://artofproblemsolving.com/community/c6h2389832p19615716 by Rickyminer and a solution to a similar problem https://artofproblemsolving.com/community/c6h347925p1865700 by Pathological in AOPS.

Case 1: $\gcd(n,2021)=1$

We proceed as Minh Hien did. Since $\gcd(n,n+2021)=1$, the equation $$ n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021)) \ \ (1) $$ gives $n+2021 | n+1-\phi(n)$. This is a contradiction.

Case 2: $\gcd(n,2021)=43$

We write $n=43k$. We have $\gcd(k,47)=1$, the equation (1) becomes $$ k(43k+1-\phi(43k))=(k+47)(43k+2022-\phi(43(k+47)). $$ Since $\gcd(k,k+47)=1$, there is a positive integer $t<43$ such that $$ 43k+1-\phi(43k)=t(k+47), $$ $$ 43k+2022-\phi(43(k+47))=tk. $$ By subtracting the second from the first, we have $$ \phi(43(k+47))-\phi(43k)=47(t+43). $$ Since $42$ divides the LHS, we have $t=41$. This gives $$ \phi(43k)=2k-1926 $$ $$ \phi(43(k+47))=2k+2022. $$ Let $k+47=43^e(k+47)_{43}$ where $\gcd((k+47)_{43},43)=1$. Let $k=43^fk_{43}$ where $\gcd(k_{43},43)=1$. We obtain $$ 43^{e-1}\phi((k+47)_{43})-43^{f-1}\phi(k_{43})=47\cdot 2. \ \ (2) $$ One of the two terms on the LHS must be $2$ mod $4$. If the first term is $2$ mod $4$, then $(k+47)_{43}$ is $p^a$, $2p^a$, or $4$ for odd prime $p$. For these numbers $\phi((k+47)_{43})/(k+47)_{43}$ is usually large. To be precise, we have the inequality $$ \frac{\phi(43(k+47))}{43(k+47)} = \frac{2k+2022}{43(k+47)} \geq \left(1-\frac1{43}\right) \cdot \frac13. $$ The inequality gives $k\leq 113$. We leave this to brute force check.

If the second term of (2) is $2$ mod $4$, $$ \frac{\phi(43k)}{43k}=\frac{2k-1926}{43k} \geq \left(1-\frac1{43}\right)\frac13 $$ does not have a solution.

Case 3: $\gcd(n,2021)=47$

We proceed similarly as in Case 2. The equation (1) becomes $$ k(47k+1-\phi(47k))=(k+43)(47k+2022-\phi(47(k+43)). $$ Write $n=47k$, $gcd(k,43)=1$. We obtain $$ \phi(47k)=2k-1934, $$ $$ \phi(47(k+43))=2k+2022, $$ and $$ 47^{e-1}\phi((k+43)_{47})-47^{f-1}\phi(k_{47})=43\cdot 2. \ \ (3) $$ If the first term is $2$ mod $4$, then $(k+43)_{47}$ is $p^a$, $2p^a$, or $4$ for odd prime $p$. Then we have $$ \frac{\phi(47(k+43))}{47(k+43)}=\frac{2k+2022}{47(k+43)} \geq \left(1-\frac1{47}\right)\cdot \frac13. $$ The last inequality gives $k\leq 102$. We leave this to a brute force check.

If the second term of (3) is $2$ mod $4$, then we have no solution similarly as in Case 2.

Case 4: $\gcd(n,2021)=2021$

We write $n=2021k$. The equation (1) becomes $$ k(2021k+1-\phi(2021k))=(k+1)(2021k+2022-\phi(2021(k+1)). $$ Proceeding as in Case 2, we have $$ \phi(2021k)=178k-1842, $$ $$ \phi(2021(k+1))=178k+2022, $$ and $$ 43^{e_1-1}47^{e_2-1}\phi((k+1)_{43,47}) - 43^{f_1-1}47^{f_2-1}\phi(k_{43,47})=2. \ \ (4) $$ If the first term is $2$ mod $4$, we have $(k+1)_{43,47}$ is $p^a$, $2p^a$, or $4$ for odd prime $p$. Then $$ \frac{\phi(2021(k+1))}{2021(k+1)}=\frac{178k+2022}{2021(k+1)} \geq \left(1-\frac1{43}\right)\left(1-\frac1{47}\right)\frac13. $$ The last equality gives $k\leq 2$. But, this does not satisfy the equality above.

Brute force cases

The cases with brute force checking left are covered with a Python code that there are no solutions.