Fermat's little theorem and Euler's theorem

Two classical theorems are the arithmetic heart of RSA: Fermat’s one for prime moduli and its generalisation due to Euler for arbitrary moduli.

Theorem — Fermat's little theorem

If $p$ is prime and $\mathrm{mcd}(a,p)=1$, then $a^{p-1} \equiv 1\pmod p.$

Theorem — Euler

Let $\varphi(n)$ be the number of integers in $\{1,2,\ldots,n\}$ coprime with $n$ (Euler’s totient function). If $\mathrm{mcd}(a,n)=1$, then $a^{\varphi(n)} \equiv 1\pmod n.$

For a historical re-reading of Fermat and Euler on modular residues see Stillwell (ch. 3).

Computing $\varphi(n)$. If $n = p\cdot q$ with $p,q$ distinct primes, $\varphi(n) = (p-1)(q-1)$. Example: $\varphi(11\cdot 13) = 10\cdot 12 = 120$.

Links

Topics: Distribuzioni probabilita
Concepts: Aritmetica modulare · Funzione di eulero
Skills: Usare formule
People: Leonhard Euler (Eulero) · Pierre de Fermat