I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree

80 Views Asked by At

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree.

To show that $n$ is squarefree in my problem, I want to show there is no prime $p$ such that $p^2 \mid n$. My thought was to attempt to show there was such a prime $p$ and obtain contradiction.

Note: I think I understand why if $n$ is composite, then $n \mid (n - 1)!$; I saw a question on stackexchange that proved as much.

1

There are 1 best solutions below

2
On

If $n$ contains a factor of $p^2$ for some prime $p$, then $p \mid \varphi(n)$. Since $(n - 1, n) = 1$, $p$ cannot divide $n - 1$, so $\varphi(n)$ cannot divide $n - 1$.