Piccolo teorema di Fermat
Cos'è il piccolo teorema di Fermat
Dato un intero a e un numero primo p, vale la congruenza $$ a^p ≡ a \mod p $$
Esempio
Ho l'intero a=6 e il numero primo p=2
$$ a^p=6^2=36 $$
Il resto della divisione 36/2 è 0. Il resto della divisione 6/2 è 0.
Quindi, i numeri 6 e 36 divisi per 2 hanno lo stesso resto (r=0) e sono congruenti modulo 2.
$$ 6^2 ≡ 6 \mod 2 $$
A cosa serve il Teorema di Fermat? E' molto utile per ridurre l'esponente nel calcolo delle potenze quando il numero è molto grande. L'unico limite è che si applica soltanto quando il modulo è un numero primo.
Corollario del piccolo teorema di Fermat
Un importante corollario del piccolo teorema di Fermat è il seguente:
Dati due numeri interi co-primi a e p, vale la congruenza $$ (a,p)=1 \rightarrow a^{p-1}=1 \mod p $$
Esempio
Ho l'intero a=4 e il numero primo p=3
Sono due numeri coprimi perché il loro Massimo Comune Divisore è uno.
$$ (4,3)=1 $$
Secondo il corollario del piccolo teorema di Fermat.
$$ a^{p-1}=4^{3-1}=4^2=16 $$
La divisione 16/3 ha resto 1.
Quindi, 16 è congruente a 1 con modulo 3.
$$ 16 ≡ 1 \mod 3 $$
Un esempio pratico
Esempio 1
Devo calcolare il resto della divisione di 519 per 3
$$ 5^{19} \mod 3 $$
Riscrivo la congruenza in questa forma equivalente
$$ (5^6)^3 \cdot 5 \mod 3 $$
Spiegazione. L'esponente 19 diviso 3 è uguale a 6 con resto 1.
Applico il teorema di Fermat perché (56)3 ha lo stesso esponente del modulo 3
$$ 5^6 \cdot 5 \mod 3 $$
$$ 5^7 \mod 3 $$
Semplifico la congruenza per applicare il teorema di Fermat
$$ (5^2)^3 \cdot 5 \mod 3 $$
Spiegazione. L'esponente 7 diviso 3 è uguale a 2 con resto 1.
Poi applico il teorema di Fermat tra (52)3 e 3
$$ 5^2 \cdot 5 \mod 3 $$
$$ 5^3 \mod 3 $$
Applico di nuovo il teorema di Fermat e ottengo
$$ 5 \mod 3 $$
Esempio 2
Devo calcolare il resto della divisione di 4526236 per 7.
Innanzitutto, posso semplificare la base della potenza sostituendola con il suo modulo 7.
$$ 4^{236} \mod 7 $$
Spiegazione. Il numero 4526 diviso 7 ha come resto 4. Pertanto, posso scrivere il numero 4526 come 4 mod 7. E' del tutto equivalente. $$ 4526 ≡ 4 \mod 7 $$
Riscrivo la congruenza in questa forma equivalente
$$ (4^{33})^7 \cdot 4^5 \mod 7 $$
Spiegazione. L'esponente 236 diviso 7 è uguale a 33 con resto 5.
Applico il piccolo teorema di Fermat
$$ 4^{33} \cdot 4^5 \mod 7 $$
$$ 4^{38} \mod 7 $$
Semplifico di nuovo
$$ (4^5)^7 \cdot 4^3 \mod 7 $$
Spiegazione. L'esponente 38 diviso 7 è uguale a 5 con resto 3.
Applico il piccolo teorema di Fermat
$$ 4^5 \cdot 4^3 \mod 7 $$
$$ 4^8 \mod 7 $$
Semplifico di nuovo
$$ 4^7 \cdot 4 \mod 7 $$
Spiegazione. L'esponente 8 diviso 7 è uguale a 1 con resto 1.
Applico il piccolo teorema di Fermat
$$ 4 \cdot 4 \mod 7 $$
$$ 4^2 \mod 7 $$
Essendo l'esponente inferiore, calcolo la divisione 42 / 7 per trovare il resto modulo 7
$$ 16 \mod 7 $$
$$ 2 \mod 7 $$
In conclusione, il resto della divisione 4526236 / 7 è 2.
E così via.
