Piccolo teorema di Fermat

Cos'è il piccolo teorema di Fermat

Dato un numero primo $ p $ e un intero $ a $ non divisibile per $ p $, allora vale la congruenza $$ a^{p-1} ≡ 1 \mod p $$

Questa è la forma principale del teorema dove $ p $ e $ a $ sono co-primi ossia relativamente primi cioé $ MCD(a,p) = 1 $.

Nota. Per il piccolo teorema di Fermat, dire che $ a $ e $ p $ sono coprimi è esattamente la stessa cosa che dire che $ a $ non è divisibile per $ p $, perché $ p $ è primo e quindi non può avere altri divisori oltre a 1 e sé stesso.

Esiste anche una forma più generale che è valida per tutti gli interi $ a $, anche quelli divisibili per $ p $.:

$$ a^p ≡ a \mod p $$

Questa formula si ottiene moltiplicando entrambi i lati della congruenza $ a^{p-1} \equiv 1 \mod p $ per $ a $

$$ a^{p-1} \cdot a ≡ 1 \cdot a \mod p $$

$$ a^p ≡ a \mod p $$

In questo caso, se $a $ è divisibile per $ p $, allora entrambi i lati della congruenza sono zero modulo $ p $, quindi la proprietà è ovvia.

Esempio

In questo esempio il modulo è un numero primo $ p=2 $ e $ a = 5 $ non è divisibile per $ p $. Il teorema dice che:

$$ 5^{2-1} ≡ 1 \mod 2 $$

$$ 5 ≡ 1 \mod 2 $$

Siccome il resto della divisione di 5 per 2 è 1, la congruenza è verificata.

Esempio 2

Considero il numero primo $ p=2 $ e l'intero $ a=6 $ che è divisibile per $ p $.

In questo caso posso usare la formula generale.

$$ 6^2 ≡ 6 \mod 2 $$

$$ 36 ≡ 6 \mod 2 $$

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.

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. Quindi, il piccolo teorema di Fermat è utilissimo per test di primalità e crittografia (tipo RSA).

Alcuni esempi

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 $$

Esempio 2

Devo calcolare il resto della divisione di 5¹⁹ 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é (5⁶)³ 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 (5²)³ e 3

$$ 5^2 \cdot 5 \mod 3 $$

$$ 5^3 \mod 3 $$

Applico di nuovo il teorema di Fermat e ottengo

$$ 5 \equiv 2 \mod 3 $$

Esempio 3

Devo calcolare il resto della divisione di 4526²³⁶ 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 4² / 7 per trovare il resto modulo 7

$$ 16 \mod 7 $$

$$ 2 \mod 7 $$

In conclusione, il resto della divisione 4526²³⁶ / 7 è 2.

Il piccolo teorema di Fermat nel caso dei numeri primi

Se \( p \) è un numero primo, il teorema di Fermat afferma che, per ogni intero \( a \) non divisibile per \( p \), vale la seguente congruenza:

$$ a^{p-1} ≡ 1 \mod p $$

Se invece \( p \) è un numero composto, si verifica la relazione:

$$ a^p ≡ a \mod p $$

Ora vediamo il perché,

La spiegazione

L’idea chiave sta nel concetto di aritmetica modulare e di gruppo moltiplicativo.

Quando ho un numero primo \( p \), gli interi da 1 a \( p-1 \) (quindi escluso lo zero) formano un gruppo moltiplicativo modulo \( p \) ossia $ (\mathbb{Z}^*_p, \cdot ) $.

Questo vuol dire che ogni elemento non nullo in questo insieme ha un inverso moltiplicativo, e l'ordine del gruppo (cioè numero di elementi) è pari a \( p-1 \).

Ora, c'è un teorema dell’algebra che dice che se ho un gruppo e prendo un qualsiasi elemento \( a \), l'ordine dell'elemento, cioè il più piccolo esponente che lo fa diventare 1, deve dividere l’ordine del gruppo.

In questo caso significa che:

\[ a^{p-1} \equiv 1 \ (\text{mod} \ p) \]

Questo perché l’ordine del gruppo è proprio \( p-1 \). E quindi l’esponente deve essere un multiplo di questo valore.

Quindi, elevando qualsiasi elemento del gruppo a \( p-1 \) ottengo sempre 1 modulo \( p \).

$$ a^{p-1} ≡ 1 \mod p $$

E questo spiega la formula del teorema di Fermat quando il modulo \( p \) è un numero primo.

Nota. Questa relazione è vera solo per i numeri primi. Tuttavia, è soddisfatta anche da alcuni numeri composti per certe basi $ a $. Questi numeri composti "imitano" i numeri primi e per questo sono chiamati pseudoprimi di Fermat.

Esempio

Considero un numero primo piccolo per ragionare meglio: \( p = 7 \).

Ora prendo tutti i numeri interi da 1 a \( p-1 \), cioè:

\[ 1, 2, 3, 4, 5, 6 \]

Questi numeri, sotto moltiplicazione modulo 7, formano un gruppo: cioè, ogni numero ha un inverso, e se moltiplico due qualsiasi di loro ottiengo sempre un numero che sta in questo stesso insieme.

Ora, l’idea chiave è che questi numeri, se li elevo a un certo esponente, iniziano a ripetersi ciclicamente.

Il ciclo massimo possibile (cioè il numero dopo cui tutti i numeri tornano uguali a 1) è esattamente \( p-1 \). Questo valore è detto ordine del gruppo.

Ad esempio, vediamo con \( a = 3 \):

Potenza	Valore mod 7
\( 3^1 \)	3 ≡ 3 (mod 7)
\( 3^2 \)	9 ≡ 2 (mod 7)
\( 3^3 \)	27 ≡ 6 (mod 7)
\( 3^4 \)	81 ≡ 4 (mod 7)
\( 3^5 \)	243 ≡ 5 (mod 7)
\( 3^6 \)	729 ≡ 1 (mod 7)

Dopo 6 passi (cioè \( p-1 = 6 \)), siamo tornati a 1. Questo non è un caso: succede per qualsiasi numero intero che non sia divisibile per \( p \).

Quindi, l'ordine di questo elemento (a=3) è 6 ed è un divisore dell'ordine del gruppo che è sempre 6.

Nota. Se invece provo con un numero non primo (tipo modulo 8 al posto di 7), questa proprietà salta, perché alcuni numeri perderanno il loro inverso moltiplicativo.

Ora vediamo cosa accade prendendo \( a = 2 \):

Potenza	Valore mod 7
\( 2^1 \)	2 ≡ 2 (mod 7)
\( 2^2 \)	4 ≡ 4 (mod 7)
\( 2^3 \)	8 ≡ 1 (mod 7)
\( 2^4 \)	16 ≡ 2 (mod 7)
\( 2^5 \)	32 ≡ 4 (mod 7)
\( 2^6 \)	64 ≡ 1 (mod 7)

In questo caso, l'ordine dell'elemento (a=2) è 3, poiché servono tre passaggi affinché l'elemento risulti congruente a 1 modulo 7.

Osservo inoltre che l'ordine dell'elemento (3) è un divisore dell'ordine del gruppo (6), il quale, di conseguenza, è un suo multiplo.

Questo implica che elevando \( 2^6 \) ottengo comunque \( 1 \) modulo 7.

E così via.