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

Question

VMO 2021:

Encontrar todos los números enteros $n \geq 2$ tal que: $n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021))$

Creo que $n$ no existe.

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

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

¿Qué debo hacer ahora?

Answer 1

Hay un poco de fuerza bruta enfoque está involucrado en mi solución. Dado que se trata de una pregunta de la Olimpiada, debería haber una manera de evitar el enfoque de fuerza bruta. La idea principal de la solución viene del comentario https://artofproblemsolving.com/community/c6h2389832p19615716 por Rickyminer y una solución a un problema similar https://artofproblemsolving.com/community/c6h347925p1865700 por Patológico en AOPS.

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

Procedemos como Minh Hien. Desde $\gcd(n,n+2021)=1$ la ecuación $$ n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021)) \ \ (1) $$ da $n+2021 | n+1-\phi(n)$ . Esto es una contradicción.

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

Escribimos $n=43k$ . Tenemos $\gcd(k,47)=1$ la ecuación (1) se convierte en $$ k(43k+1-\phi(43k))=(k+47)(43k+2022-\phi(43(k+47)). $$ Desde $\gcd(k,k+47)=1$ existe un número entero positivo $t<43$ tal que $$ 43k+1-\phi(43k)=t(k+47), $$ $$ 43k+2022-\phi(43(k+47))=tk. $$ Restando la segunda de la primera, tenemos $$ \phi(43(k+47))-\phi(43k)=47(t+43). $$ Desde $42$ divide el LHS, tenemos $t=41$ . Esto da $$ \phi(43k)=2k-1926 $$ $$ \phi(43(k+47))=2k+2022. $$ Sea $k+47=43^e(k+47)_{43}$ donde $\gcd((k+47)_{43},43)=1$ . Sea $k=43^fk_{43}$ donde $\gcd(k_{43},43)=1$ . Obtenemos $$ 43^{e-1}\phi((k+47)_{43})-43^{f-1}\phi(k_{43})=47\cdot 2. \ \ (2) $$ Uno de los dos términos del LHS debe ser $2$ mod $4$ . Si el primer término es $2$ mod $4$ entonces $(k+47)_{43}$ es $p^a$ , $2p^a$ ou $4$ para impar prime $p$ . Para estos números $\phi((k+47)_{43})/(k+47)_{43}$ suele ser grande. Para ser precisos, tenemos la desigualdad $$ \frac{\phi(43(k+47))}{43(k+47)} = \frac{2k+2022}{43(k+47)} \geq \left(1-\frac1{43}\right) \cdot \frac13. $$ La desigualdad da $k\leq 113$ . Dejamos esto a la comprobación de fuerza bruta.

Si el segundo término de (2) es $2$ mod $4$ , $$ \frac{\phi(43k)}{43k}=\frac{2k-1926}{43k} \geq \left(1-\frac1{43}\right)\frac13 $$ no tiene solución.

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

Procedemos de forma similar al caso 2. La ecuación (1) se convierte en $$ k(47k+1-\phi(47k))=(k+43)(47k+2022-\phi(47(k+43)). $$ Escriba a $n=47k$ , $gcd(k,43)=1$ . Obtenemos $$ \phi(47k)=2k-1934, $$ $$ \phi(47(k+43))=2k+2022, $$ y $$ 47^{e-1}\phi((k+43)_{47})-47^{f-1}\phi(k_{47})=43\cdot 2. \ \ (3) $$ Si el primer término es $2$ mod $4$ entonces $(k+43)_{47}$ es $p^a$ , $2p^a$ ou $4$ para impar prime $p$ . Entonces tenemos $$ \frac{\phi(47(k+43))}{47(k+43)}=\frac{2k+2022}{47(k+43)} \geq \left(1-\frac1{47}\right)\cdot \frac13. $$ La última desigualdad da $k\leq 102$ . Dejamos esto a una comprobación de fuerza bruta.

Si el segundo término de (3) es $2$ mod $4$ entonces no tenemos solución, como en el caso 2.

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

Escribimos $n=2021k$ . La ecuación (1) se convierte en $$ k(2021k+1-\phi(2021k))=(k+1)(2021k+2022-\phi(2021(k+1)). $$ Procediendo como en el caso 2, tenemos $$ \phi(2021k)=178k-1842, $$ $$ \phi(2021(k+1))=178k+2022, $$ y $$ 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) $$ Si el primer término es $2$ mod $4$ tenemos $(k+1)_{43,47}$ es $p^a$ , $2p^a$ ou $4$ para impar prime $p$ . Entonces $$ \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. $$ La última igualdad da $k\leq 2$ . Pero esto no satisface la igualdad anterior.

Casos de fuerza bruta

Los casos con comprobación de fuerza bruta a la izquierda están cubiertos con un código Python que no hay soluciones.