Prove Fermat's Theorem: if $p$ is prime and $(x, p)=1$ then $x^{p-1} \equiv 1(\bmod p)$.

Let $n$ and $x$ be positive integers with $(x, n)=1$. Show that if $n=m p$ where $p$ is prime and $(m, p)=1$, then

$$x^{n-1} \equiv 1 \quad(\bmod p) \quad \text { if and only if } \quad x^{m-1} \equiv 1 \quad(\bmod p)$$

Now assume that $n$ is a product of distinct primes. Show that $x^{n-1} \equiv 1(\bmod n)$ if and only if, for every prime divisor $p$ of $n$,

$$x^{(n / p)-1} \equiv 1 \quad(\bmod p) .$$

Deduce that if every prime divisor $p$ of $n$ satisfies $(p-1) \mid(n-1)$, then for every $x$ with $(x, n)=1$, the congruence

$$x^{n-1} \equiv 1 \quad(\bmod n)$$

holds.