Finding a $n \in \mathbb{N}$ such that $\frac{\phi(n+1)}{\phi(n)} = 4$

Question

• Let $\phi$ denote the Euler Phi Function.

• How do I find a $n \in \mathbb{N}$ such that $\frac{\phi(n+1)}{\phi(n)} = 4$. I can find $n \in\mathbb{N}$ such that $\frac{\phi(n+1)}{\phi(n)}=3$, for example, $n=12$ works.

• How does one go about constructing such an $n$??

Answer 1

This answer is just a summary of some points mentioned in the comments, a way to numerically find solutions, some references and a short summary of what I found in the litterature about this and similar questions.

---

As pointed out by lhf, the solutions to $\frac{\phi(n+1)}{\phi(n)} = 4$ is sequence A172314 in OEIS. The solutions for $n\leq 10^7$ are

$$\{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\}$$

These solutions was found using mathematical software and took a minute on my laptop. See a simple Mathematica code in the end that does this computation.

I guess a numerical solution is not what you are after, however solving it "by-brain" seems like a hard problem since we need information about the prime-factors of both $n$ and $n+1$ to do so. There is no simple relationship between these unless for very special cases. It's tempting to try some of these special cases like for example $n$ being a prime on the the form $2^k\pm 1$ (Fermat or Mersenne primes), however this does not lead to a solution. Numerically it seems like $n$ has to be a product of at least $4$ distinct primes which rules out most of the other simple cases we could try.

It should be noted that very little is known about the (I presume) simpler question that asks to find solutions to $\phi(n+1) = \phi(n)$ and more generally $\phi(n+k) = \phi(n)$. Some references are given below (taken from the OEIS page linked above):

• K. Miller, Solutions of $\phi(n) = \phi(n+1)$ for $1 \leq n \leq 500000$. De Pauw University, 1972.

• V. L. Klee, Jr., Some remarks on Euler's totient function, Amer. Math. Monthly, 54 (1947), 332.

• M. Lal and P. Gillard, On the Equation $\phi(n) = \phi(n+k)$, Math. Comp. 26 (1972), 579-583.

• L. Moser, Some equations involving Euler's totient function, Amer. Math. Monthly, 56 (1949), 22-23.

As you can see from these references most of the work is simply reporting solutions found numerically. There are some special cases where analytical solutions are know. Some examples mentioned in the papers above are:

• $\phi(n) = \phi(n+2)$ is satisfied by $n=2(2p-1)$ if both $p$ and $2p-1$ are odd primes, and by $n = 2^{2^a+1}$ if $2^{2^a}+1$ is a Fermat prime.

• The equation $\phi(n) + 2 = \phi(n+2)$ is satisfied if $n$ and $n+2$ are primes, if $n$ has the form $4p$ where $p$ and $2p+1$ are primes, and if $n=2M_p$ where $M_p = 2^p-1$ is a Mersenne prime.

• If $n=2^a+1$ is a prime and $k=2^{a+1}-n$, then $\phi(n) = \phi(n+k)$.

• If $n=2^a3^b+1$ is a prime and $k=2^{a+1}3^{b}-1$, then $\phi(n) = \phi(n+k)$.

• If $n=3k$ and $2$ and $3$ do not divide $k$ then $\phi(3k) = \phi(4k)$.

• If $n=2p$ where $p$ is an odd prime and $(p+1)/2$ is a prime other than $3$, and $k=3(p+1)/2-n$ then $\phi(n) = \phi(n+k)$.

• If $n=3p$ where $p$ is a prime other than $3$ and $(p+1)/2$ is a prime other than $5$, and $k=5(p+1)/2-n$ then $\phi(n) = \phi(n+k)$.

---

Mathematica code to find all solutions below a given $n$:

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