# If $\phi(n)$ divides $n-1$, prove that $n$ is a product of distinct prime numbers

If $\phi(n)$ divides $n-1$, prove that $n$ is a product of distinct prime numbers (such as number is also called square-free, as it is divisible by no square greater than $1$).

#### Solutions Collecting From Web of "If $\phi(n)$ divides $n-1$, prove that $n$ is a product of distinct prime numbers"

If $\displaystyle n=\prod_ip_i^{e_i}$, then $\displaystyle\phi(n)=\prod_i(p_i-1)p_i^{e_i-1}$

Therefore,
$$\frac{n-1}{\phi(n)}\prod_ip_i^{e_i-1}(p_i-1)=n-1$$
If any $e_i\gt1$, then $p_i^{e_i-1}$ divides both $n$ and $n-1$. Contradiction.

Hint: If $p^2|n$ then $p|\phi(n)$. Can $\phi(n)|n-1$ in that case?