Encontrar un $n \in \mathbb{N}$ tal que $\frac{\phi(n+1)}{\phi(n)} = 4$

Question

• Dejemos que $\phi$ denotan la función Phi de Euler.

• ¿Cómo puedo encontrar un $n \in \mathbb{N}$ tal que $\frac{\phi(n+1)}{\phi(n)} = 4$ . Puedo encontrar $n \in\mathbb{N}$ tal que $\frac{\phi(n+1)}{\phi(n)}=3$ por ejemplo, $n=12$ funciona.

• ¿Cómo se construye este tipo de $n$ ??

Answer 1

Esta respuesta es sólo un resumen de algunos puntos mencionados en los comentarios, una forma de encontrar numéricamente las soluciones, algunas referencias y un breve resumen de lo que he encontrado en la literatura sobre esta y otras cuestiones similares.

---

Como señala lhf, las soluciones a $\frac{\phi(n+1)}{\phi(n)} = 4$ es la secuencia A172314 en la OEIS. Las soluciones para $n\leq 10^7$ son

$$\{1260, 13650, 17556, 18720, 24510, 42120, 113610, 244530, 266070,\\ 712080, 749910, 795690, 992250, 1080720, 1286730, 1458270, \\1849470, 2271060, 2457690, 3295380, 3370770, 3414840, 3714750,\\ 4061970, 4736490, 5314050, 5827080, 6566910, 6935082, 7303980,\\ 7864080, 7945560, 8062860, 8223150, 8559720, 9389040, 9774030\}$$

Estas soluciones fueron encontradas usando un software matemático y tomaron un minuto en mi laptop. Al final se puede ver un sencillo código de Mathematica que realiza este cálculo.

Supongo que una solución numérica no es lo que buscas, sin embargo resolverlo "by-brain" parece un problema difícil ya que necesitamos información sobre los factores primos de ambos $n$ y $n+1$ para hacerlo. No existe una relación sencilla entre ellas, salvo en casos muy especiales. Es tentador probar algunos de estos casos especiales como por ejemplo $n$ siendo un primo de la forma $2^k\pm 1$ (primos de Fermat o Mersenne), sin embargo esto no conduce a una solución. Numéricamente parece que $n$ tiene que ser un producto de al menos $4$ primos distintos, lo que descarta la mayoría de los otros casos sencillos que podríamos probar.

Hay que señalar que se sabe muy poco sobre la pregunta (supongo) más sencilla que pide encontrar soluciones a $\phi(n+1) = \phi(n)$ y en general $\phi(n+k) = \phi(n)$ . A continuación se ofrecen algunas referencias (tomadas de la página de la OEIS enlazada anteriormente):

• K. Miller, Soluciones de $\phi(n) = \phi(n+1)$ para $1 \leq n \leq 500000$ . Universidad De Pauw, 1972.

• V. L. Klee, Jr, Algunas observaciones sobre la función totiente de Euler , Amer. Math. Monthly, 54 (1947), 332.

• M. Lal y P. Gillard, Sobre la ecuación $\phi(n) = \phi(n+k)$ Math. Comp. 26 (1972), 579-583.

• L. Moser, Algunas ecuaciones que implican la función totiente de Euler , Amer. Math. Monthly, 56 (1949), 22-23.

Como se puede ver en estas referencias, la mayoría de los trabajos se limitan a informar de las soluciones encontradas numéricamente. Hay algunos casos especiales en los que se conocen soluciones analíticas. Algunos ejemplos mencionados en los trabajos anteriores son:

• $\phi(n) = \phi(n+2)$ se satisface con $n=2(2p-1)$ si ambos $p$ y $2p-1$ son primos Impares, y por $n = 2^{2^a+1}$ si $2^{2^a}+1$ es un primo de Fermat.

• La ecuación $\phi(n) + 2 = \phi(n+2)$ se cumple si $n$ y $n+2$ son primos, si $n$ tiene la forma $4p$ donde $p$ y $2p+1$ son primos, y si $n=2M_p$ donde $M_p = 2^p-1$ es un primo de Mersenne.

• Si $n=2^a+1$ es un primo y $k=2^{a+1}-n$ entonces $\phi(n) = \phi(n+k)$ .

• Si $n=2^a3^b+1$ es un primo y $k=2^{a+1}3^{b}-1$ entonces $\phi(n) = \phi(n+k)$ .

• Si $n=3k$ y $2$ y $3$ no dividir $k$ entonces $\phi(3k) = \phi(4k)$ .

• Si $n=2p$ donde $p$ es un primo impar y $(p+1)/2$ es un primo distinto de $3$ y $k=3(p+1)/2-n$ entonces $\phi(n) = \phi(n+k)$ .

• Si $n=3p$ donde $p$ es un primo distinto de $3$ y $(p+1)/2$ es un primo distinto de $5$ y $k=5(p+1)/2-n$ entonces $\phi(n) = \phi(n+k)$ .

---

Código de Mathematica para encontrar todas las soluciones por debajo de un determinado $n$ :

n = 1000000;
philist = Table[EulerPhi[i], {i, 1, n+1}];
Do[
    If[ philist[[i + 1]]/philist[[i]] == 4, Print[i] ];
 , {i, 1, n}]