If $\phi(n) |n-1$, then $n$ is square-free and either prime or has at least three prime factors If $\phi(n) |n-1$ then $n$ is square-free. Show also that $n$ is either a prime or has at least three prime factors.
$n$ prime if is obvious: $\phi(p)|p-1$ since $\phi(p)=p-1$.
 A: If $n=\prod_i p_i^{a_i}$, where $p_i$ are distinct primes, we have $\phi(n) = \prod_i p_i^{a_i-1}(p_i-1)$. From the statement of the problem, this gives us that
$$\dfrac{-1+\prod_i p_i^{a_i}}{\prod_i p_i^{a_i-1}(p_i-1)} \in \mathbb{Z}$$
This means $p_i^{a_i-1}$ divides $n-1$, but we also have that $p_i^{a_i-1}$ divides $n$. Hence, $p_i^{a_i-1}$ divides $n-(n-1)$. This gives us that $a_i$ has to be $1$.
Hence, $n$ is square free, i.e., $n = \prod_i p_i$, where $p_i$ are distinct primes.

For the second part, if $n=pq$, we have $\phi(n) = (p-1)(q-1)$, which divides $pq-1$, i.e.,
$$\dfrac{pq-1}{(p-1)(q-1)} \in \mathbb{Z} \implies \dfrac{(p-1)(q-1) + p+q - 2}{(p-1)(q-1)} \in \mathbb{Z}$$
Hence,
$$\dfrac{(p+q-2)}{(p-1)(q-1)} \in \mathbb{Z} \implies \dfrac1{p-1} + \dfrac1{q-1} \in \mathbb{Z}$$
This forces $p=q=2$ or $p=q=3$, which is not possible since $p$ and $q$ are distinct primes. Hence, we have $n = \prod_{i=1}^m p_i$, where $p_1 < p_2 < \cdots < p_m$ are primes with $m\neq 2$.
A: Hint : Show that if $p^2$ divides $n$ then $p$ divides $\phi(n)$. Then deduce the first statement.
For the second statement, if $p$ and $q$ are two distinct primes then $\phi(pq)=(p-1)(q-1)$. If this number divides $pq-1=(p-1)q+(q-1)$ then $q-1$ divides $(p-1)q$ but $gcd(q-1,q)=1$ so $q-1$ divides $p-1$. The same being true for $q$ and $p$ reversed you have $p=q$ which is a contradiction.
