= Solution
For a <prime number> $p$ and an <integer> $x$ <coprime> to $p$, multiplication by $x$ permutes the nonzero residue classes modulo $p$. Indeed, $ax\equiv bx\pmod p$ implies $a\equiv b\pmod p$, and none of the products is zero. Taking the product over the $p-1$ classes gives
$$
x^{p-1}(p-1)!\equiv(p-1)!\pmod p.
$$
The <factorial> is <coprime> to $p$ and can be cancelled, proving <Fermat little theorem>: $\boxed{x^{p-1}\equiv1\pmod p}$.
Now $n=mp$ and $x$ is <coprime> to $n$, so it is <coprime> to $p$. Since $(n-1)-(m-1)=m(p-1)$, the proved theorem gives
$$
x^{n-1}=x^{m-1}(x^{p-1})^m\equiv x^{m-1}\pmod p.
$$
Thus the two specified <integer congruences> modulo $p$ are equivalent. In this particular step the additional hypothesis $(m,p)=1$ is not needed; it will hold for the squarefree factorization used next.
If $n$ is a <squarefree integer>, its distinct <prime factors> are pairwise <coprime>. Consequently $n$ divides $x^{n-1}-1$ exactly when every <prime factor> does. Applying the preceding equivalence with $m=n/p$ proves
$$
\boxed{x^{n-1}\equiv1\pmod n\quad\Longleftrightarrow\quad
x^{(n/p)-1}\equiv1\pmod p\text{ for every }p\mid n.}
$$
Finally retain this squarefree hypothesis. If $p-1$ divides $n-1$, write $n-1=k_p(p-1)$. <Fermat little theorem> gives $x^{n-1}=(x^{p-1})^{k_p}\equiv1\pmod p$ for every <prime factor>. Their pairwise coprimality then gives $\boxed{x^{n-1}\equiv1\pmod n}$. For composite $n$ this is the sufficient direction of the <Korselt criterion> for a <Carmichael number>; primality is not excluded by the requested implication.
Back to article page
