Il teorema di Eulero
Dati due numeri interi $ a $ e $ n $ relativamente primi (cioè gcd(a, n) = 1), vale la seguente relazione: \[a^{\varphi(n)} \equiv 1 \mod n\] dove φ(n) è la funzione di Eulero, che conta quanti numeri interi minori di $ n $ sono relativamente primi con n.
Il teorema di Eulero è un'estensione del piccolo teorema di Fermat, che permette di lavorare con moduli non necessariamente primi.
Secondo il piccolo teorema, se $ p $ è un numero primo e $ a $ è un intero non divisibile da $ p $, allora:
\[ a^{p-1} \equiv 1 \mod p \]
Tuttavia, questo vale solo per numeri $ p $ primi.
Il Teorema di Eulero generalizza questa proprietà ed estende la validità della congruenza a qualsiasi numero intero positivo $ n $, utilizzando la funzione di Eulero $ φ(n) $.
\[a^{\varphi(n)} \equiv 1 \mod n\]
A cosa serve? Il teorema di Eulero è fondamentale nella crittografia RSA, dove si utilizza la funzione di Eulero per calcolare gli esponenti nelle operazioni di crittografia e decrittografia.
Un esempio pratico
Considero $ n = 20 $, che non è un numero primo.
Scelgo un numero $ a = 3 $, coprimo con 20.
Calcolo la funzione di Eulero φ(20).
$$ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \cdots \cdot \left(1 - \frac{1}{p_k}\right) $$
Dove \(p_1, p_2, \dots, p_k\) sono i fattori primi di \(n\).
In questo caso $ n= 20 $ che può essere scomposto in fattori primi $ 20 = 2^2 \cdot 5 $, quindi i fattori primi sono $ p_1=2 $ e $ p_2=5 $
$$ \phi(20) = 20 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) $$
$$ \phi(20) = 20 \cdot \frac{2-1}{2} \cdot \frac{5-1}{5} $$
$$ \phi(20) = 20 \cdot \frac{1}{2} \cdot \frac{4}{5} $$
$$ \phi(20) = 20 \cdot \frac{4}{10} $$
$$ \phi(20) = 2 \cdot 4 $$
$$ \phi(20) = 8 $$
La funzione di Eulero è $ \phi(20) = 8 $, questo significa che $ n=20 $ ha 8 numeri relativamente primi da 1 a 20.
Verifica. I divisori di 20 sono: 1, 2, 4, 5, 10, 20. Quindi, per esclusione, i numeri coprimi con 20 sono: 1, 3, 7, 9, 11, 13, 17, 19. Complessivamente sono 8 numeri coprimi. Dunque, la funzione di Eulero è $$ φ(20) = 8 $$
Ora verifico la congruenza del teorema di Eulero
\[a^{\varphi(n)} \equiv 1 \mod n\]
$$ 3^{\varphi(20)} \equiv 1 \mod 20 $$
$$ 3^8 \equiv 1 \mod 20 $$
Sapendo che \( 3^8 = 6561 \)
$$ 6561 \equiv 1 \mod 20 $$
Il resto della divisione \( 6561 \div 20 \) è 1. Quindi \( 6561 \equiv 1 \mod 20 \)
$$ 3^{\varphi(20)} \equiv 1 \mod 20 $$
Questo conferma il teorema di Eulero.
E così via.
