Find smallest $N_0$ such that $\phi(n)\geq 5 \; \forall n\geq N_0$

Question

Find smallest $N_0$ such that $\phi(n)\geq 5 \; \forall n\geq N_0$ where $\phi$ is Euler's Totient function

I can't think of a way to tackle this. Please help me

Answer 1

I claim $N_0=13$. If $n$ is divisible by $2^4, 3^2, 5^2, $ or a prime $p\ge7$, then by the multiplicative property of the totient function $\phi(n)\ge6$. So if $\phi(n)<6$, then $n=2^a3^b5^c$ with $0\le a\le3$ and $0\le b,c\le 1$. There are $16$ numbers of this form; only $7$ of those are above $12$, and it can be checked that for those $7$ the totient function is $6$ or more.

On the other hand $\phi(12)=4$, so $N_0>12$.

Answer 2

The inequality in one of the linked answers is wrong. The first one below has equality at 2, the second one at 6, third at 30.

$$ \phi(n) \geq \sqrt{ \frac{n}{ 2} }. $$

$$ \phi(n) \geq 2 \cdot \left( \frac{n}{6} \right)^{2/3}. $$

$$ \phi(n) \geq 8 \cdot \left( \frac{n}{30} \right)^{7/8}. $$

The first one says $N_0 = 50$ is good enough. Using a calculator for the roots, the second one says $N_0 = 24$ is good enough, while the third says $N_0 = 18$ is good enough. So, check up to 18.

see Is the Euler phi function bounded below?

I give a proof at the same question.

Answer 3

To solve this problem, we can explicitly list all $n$ such that $\phi(n) = 1, 2, 3,$ or $4$.

Recall that we can compute $\phi$ using prime factorization: if $n = 2^{x_1} 3^{x_2} 5^{x_3} \ldots$, then \begin{align*} \phi(n) &= \phi(2^{x_1}) \phi(3^{x_2}) \phi(5^{x_3}) \cdots \end{align*} The first term of the product $\phi(2^{x_1})$ is a power of $2$. Next, $\phi(3^{x_2})$ is one of $1, 2, 6, 18, \ldots$, so if $\phi(n) = 1, 2, 3, \text{ or } 4$ then the only possibility is $2$. Next, $\phi(5^{x_3})$ is one of $1, 4, 20, 100, \ldots$, so it can only be $1$ or $4$. $\phi(7^{x_4})$ and everything after that can only be $1$. So we have that $$ \phi(n) = (1, 2, \text{ or } 4) \cdot (1 \text{ or } 2) \cdot (1 \text{ or } 4) $$ And the only possibilities are in the table below: $$ \begin{array}{ccc} \phi(n) = 1 & 1 \cdot 1 \cdot 1 & n = 1, 2 \\ \phi(n) = 2 & 1 \cdot 2 \cdot 1 & n = 3, 6 \\ & 2 \cdot 1 \cdot 1 & n = 4 \\ \phi(n) = 3 & - & - \\ \phi(n) = 4 & 1 \cdot 1 \cdot 4 & n = 5, 10 \\ & 2 \cdot 2 \cdot 1 & n = 12 \\ & 4 \cdot 1 \cdot 1 & n = 8 \end{array} $$ We see that for all $n$ such that $\phi(n) = 1, 2, 3,$ or $4$, $n$ is at most $12$. So for $n \ge 13$, $\phi(n) \ge 5$.

Answer 4

We know that $\phi(n)=4$ if and only if $n=5,8,10,12$, see below. Also $\phi(n)$ is never $3$ and $\phi(n)=2$ if and only if $n=3,4$. Hence we can conclude that $\phi(n)\ge 5$ for all $n\ge 13$.

Reference: Find all $n \in \mathbb{Z^+} : \phi(n)=4$