Piccolo teorema di Fermat e teorema di Eulero

Due teoremi classici sono il cuore aritmetico di RSA: quello di Fermat per i moduli primi e la sua generalizzazione dovuta a Eulero per moduli qualsiasi.

Teorema — Piccolo teorema di Fermat

Se $p$ è primo e $\mathrm{mcd}(a,p)=1$, allora $a^{p-1} \equiv 1\pmod p.$

Teorema — Eulero

Sia $\varphi(n)$ il numero di interi in $\{1,2,\ldots,n\}$ coprimi con $n$ (funzione di Eulero). Se $\mathrm{mcd}(a,n)=1$, allora $a^{\varphi(n)} \equiv 1\pmod n.$

Per una rilettura storica di Fermat ed Eulero sui residui modulari si veda Stillwell (cap. 3).

Calcolo di $\varphi(n)$. Se $n = p\cdot q$ con $p,q$ primi distinti, $\varphi(n) = (p-1)(q-1)$. Esempio: $\varphi(11\cdot 13) = 10\cdot 12 = 120$.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Funzione di eulero
Competenze: Usare formule
Persone: Leonhard Euler (Eulero) · Pierre de Fermat