= Solution
The <Fermat-Euler theorem> states that for an <integer> $a$ and a positive <integer> $n$ with $\gcd(a,n)=1$,
$$
\boxed{a^{\varphi(n)}\equiv1\pmod n,}
$$
where the <Euler totient function> $\varphi(n)$ counts the <residue classes> coprime to $n$. For $n\ge2$, choose a <reduced residue system> $r_1,\ldots,r_{\varphi(n)}$. Multiplication by the <unit modulo n> $a$ preserves coprimality and is injective on these <residue classes>: $ar_i\equiv ar_j\pmod n$ implies $r_i\equiv r_j\pmod n$, because $a$ has a <multiplicative inverse> modulo $n$. It therefore permutes the <reduced residue system>, giving
$$
a^{\varphi(n)}\prod_i r_i\equiv\prod_i r_i\pmod n.
$$
The product is also a <unit modulo n>, so it can be cancelled. This proves the <Fermat-Euler theorem>. For $n=1$ every <modular congruence> is automatic; one may use $\varphi(1)=1$.
For a <prime number> $p$, the <Euler totient function> has value $\varphi(p)=p-1$. Thus $a^{p-1}\equiv1\pmod p$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of <Fermat's little theorem>:
$$
\boxed{a^p\equiv a\pmod p\quad\text{for every integer }a.}
$$
Finally, <Wilson theorem> states that for every <prime number> $p$, $\boxed{(p-1)!\equiv-1\pmod p}$. Its converse is also true: an <integer> $n>1$ is prime exactly when $(n-1)!\equiv-1\pmod n$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.
Back to article page
