$\varphi(n) \leq 5$, where $\varphi$ is the Eulerian function

Question

If $\varphi(n) \leq 5$, then can we find a bound for $n$ itself, where $\varphi$ is the Eulerian function?

Answer 1

Suppose the prime factors of $n$ is $p_1<\ldots<p_m$. Then $$\begin{eqnarray} \frac{5}{n}&\geq&\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_m}\right) \\ &\geq& \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)\cdots\left(1-\frac{1}{p_m}\right) \\ &=& \frac{1}{p_m}. \end{eqnarray}$$

Thus we know $n\leq 5p_m$, which means that $n=p_m,2p_m,3p_m,4p_m$ or $5p_m$, where $\varphi(n)$ can be $$p_m-1, 2(p_m-1), 4(p_m-1).$$ Therefore we know $n\leq 12$ by enumerating all possibilities.

Answer 2

It is possible to find a bound, but I can't think of a quick way other than just listing all possible values of $n$.

First note that if $n$ has prime factorization $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then an explicit formula for $\varphi(n)$ can be found:

$$\varphi(n)=p_1^{\alpha_1-1}(p_1-1)\cdot p_2^{\alpha_2-1}(p_2-1)\cdots p_k^{\alpha_k-1}(p_k-1).$$

This means that $n$ can only contain prime factors of $2,3,5$, since $7-1>5$, so any other primes would make $\varphi(n)$ too big. So write

$$n=2^{\alpha_1}\cdot3^{\alpha_2}\cdot5^{\alpha_3}$$

We cannot have over two factors of 5, since otherwise $\varphi(n)\geq 5(5-1)=20$. If we have one factor of 5, then $5-1\mid\varphi(n)$, and so the remaining factors of the form $p_i^{\alpha_i-1}(p_i-1)$ must all be equal to 1, which means that the only other prime can be 2, and its exponent must be at most 1. This implies that the only possible values of $n$ with a factor of $5$, are $n=5,10$.

The remaining values of $n$ are of the form $2^{\alpha_1}\cdot3^{\alpha_2}$. Suppose that both $\alpha_1,\alpha_2$ are nonzero. Then

$$\varphi(n)=2^{\alpha_1-1}(2-1)\cdot3^{\alpha_2-1}(3-1)=2^{\alpha_1}\cdot3^{\alpha_1-1}$$

so since $\alpha_1\geq1$, we must have that $\alpha_2-1=0$, or $\alpha_2=1$ (since $2\cdot3>5$). So $\varphi(n)=2^{\alpha_1}$ To keep this under 5, we must have that $2^{\alpha_1}=2,4$, forcing $n=6,12$ in this case.

Now the only remaining cases are when $n$ is a power of $2$ or $3$. In the former case, $$n=2^{\alpha_1}\implies \varphi(n)=2^{\alpha_1-1}=\frac{n}{2}$$ so that $\varphi(n)\leq5$ becomes equivalent to $n\leq10$. Since $n$ was a power of 2, we can only have that $n=2,4,8$.

If $n=3^{\alpha_2}$ is a power of 3, then $$\varphi(n)=3^{\alpha_2-1}\cdot2=\frac{2}{3}n,$$ and so the condition becomes that $n\leq\frac{15}{2}$, forcing $n=3$ (since $9>\frac{15}{2}$).

Finally, there is the case where $n=1$, but clearly $\varphi(1)=1\leq5$.

If we tally up all possible values of $n$, we get $n=1,2,3,4,5,6,8,10,12$. So $n\leq12$

Answer 3

In this case, it is easy to find all solutions because $\varphi(n) \leq 5$ iff $\varphi(n) =1,2,3,4$.

$\varphi(n)=1$ iff $n\in\{1,2\}$.

$\varphi(n)=2$ iff $n\in\{3,4,6\}$.

$\varphi(n)=3$ never.

$\varphi(n)=4$ iff $n\in\{5,8,10,12\}$.

So, $n\le12$.

This argument uses that $\varphi(2m)=\varphi(m)$ if $m$ is odd and $\varphi(2m)=2\varphi(m)$ if $m$ is even.