Find all naturals numbers $φ(8n)< φ(5n)$ [Answer provided - Questioning for explanation]

Question

Find all naturals numbers $φ(8n)< φ(5n)$

Answer:

then

Means $n$ is an odd number that is a multiple of 5

Question: Can I get an elaboration on how it was solved? also why did they use 4n?

Answer 1

Note that for $n > 1$, $\varphi(n)$ has a formula in terms of its prime factors.
Given $n = p_1^{a_1}\cdots p_k^{a_k}$ in the standard way, we have $$\varphi(n) = n\left(1-\dfrac{1}{p_1}\right)\cdots\left(1-\dfrac{1}{p_k}\right).$$

Now, if $5$ is already a factor of $n$, then the prime factors of $5n$ are the same as that of $n$ and thus, we get $$\varphi(5n) = 5n\left(1-\dfrac{1}{p_1}\right)\cdots\left(1-\dfrac{1}{p_k}\right) = 5\varphi(n).$$

However, $5$ does not divide $n$, then $5n$ has the additional prime factor of $5$ and thus, we get $$\varphi(5n) = 5n\left(1-\dfrac{1}{5}\right)\left(1-\dfrac{1}{p_1}\right)\cdots\left(1-\dfrac{1}{p_k}\right) = 4\varphi(n).$$

---

This gives us the correct formula for $\varphi(5n)$ as $$\varphi(5n) = \begin{cases}5\varphi(n) & 5 \mid n\\4\varphi(n) & 5 \nmid n\end{cases}$$

Note that even though we assumed $n > 1$, to begin with, the above formula does work for $n = 1$ as well. (As seen by a manual check.)

---

Similarly, by considering the case whether $2\mid n$ or not, we get the formula for $\varphi(8n)$ as $$\varphi(8n) = \begin{cases}8\varphi(n) & 2 \mid n\\4\varphi(n) & 2 \nmid n\end{cases}$$

---

Note that the above result is slightly different from what you had written.

---

The above shows you that if you want $\varphi(8n) < \varphi(5n)$, the only possibility is that $\varphi(8n) = 4\varphi(n)$ and $\varphi(5n) = 5\varphi(n)$.

Thus, these conditions force $$\boxed{2 \nmid n \text{ and } 5 \mid n}.$$

Answer 2

The final answer is correct, but the calculations used to justify the answer have an error:

If the decomposition of $n$ into a product of primes is $n=\prod_{i=1}^r p_i^{k_i}$, we have $$\frac{\varphi(n)}n=\prod_{i=1}^r\Bigl(1-\frac1{p_i}\Bigr).$$ Therefore,

• if $5\mid n$, no new prime factor is added in $5n$ w.r.t. $n$, so that $$\frac{\varphi(5n)}{5n}=\frac{\varphi(n)}{n},\quad\text{whence }\enspace\varphi(5n)=5\varphi(n).$$
• if $5\nmid n$, $5$ is a new prime factor, so $$\frac{\varphi(5n)}{5n}=\frac{\varphi(n)}{n}\cdot\Bigl(1-\frac15\Bigr)=\frac{4\varphi(n)}{5n},\quad\text{whence }\enspace\varphi(5n)=4\varphi(n).$$

Similar computations for $8$: we have to distinguish the cases $n$ odd and $n$ even.