Piccolo Teorema di Fermat: Spiegazione Semplice, Formule ed Esercizi Svolti

Calcolare la centesima potenza di un numero a mano sembra una tortura inutile. Eppure, in campi come la sicurezza informatica e l’ottimizzazione degli algoritmi, i computer si scontrano continuamente con esponenti giganteschi.

Come se ne esce senza far fondere i processori (o il nostro cervello)?
La risposta sta in un’intuizione elegante che Pierre de Fermat ebbe nel XVII secolo.

Per capirla non serve essere matematici esperti: basta immaginare il quadrante di un orologio.

Vediamo insieme come funziona questa regola e come usarla per semplificare drasticamente calcoli che, a prima vista, sembrano impossibili.

Piccolo Teorema di Fermat

Il Piccolo Teorema di Fermat afferma:

Se p è un numero primo e a è un intero non divisibile per p, allora

[math]a^{\,p-1} \equiv 1 \pmod{p}.[/math]

Equivalentemente, per ogni intero a,

[math]a^{\,p} \equiv a \pmod{p}.[/math]

Questo teorema è uno strumento potentissimo per semplificare calcoli di potenze modulo un numero primo.

Di seguito trovi 6 esercizi originali, in ordine di difficoltà crescente. Ogni esercizio è risolto passo dopo passo con commenti didattici, osservazioni strategiche e un mini‑quiz per fissare i concetti.

Esercizio 1 – Livello Base

Calcola: [math]3^{100} \bmod 7[/math].

Soluzione

Poiché 7 è primo e 3 non è divisibile per 7, il Piccolo Teorema di Fermat ci garantisce che

[math]3^{6} \equiv 1 \pmod{7}.[/math]

Ora scriviamo l’esponente 100 in funzione di 6:

[math]\displaystyle \begin{aligned}
100 &= 6 \cdot 16 + 4.
\end{aligned}[/math]

Quindi:

[math]\displaystyle \begin{aligned}
3^{100} &= 3^{\,6 \cdot 16 + 4} \\
&= (3^{6})^{16} \cdot 3^{4} \\
&\equiv 1^{16} \cdot 3^{4} \pmod{7} \\
&\equiv 81 \pmod{7}.
\end{aligned}[/math]

Poiché [math]81 = 7 \cdot 11 + 4[/math], si ha

[math]3^{100} \equiv 4 \pmod{7}.[/math]

Risultato: [math]3^{100} \bmod 7 = 4[/math].

Mini‑quiz

• Quale numero primo viene utilizzato? Risposta: 7
• Qual è il periodo garantito dal teorema? Risposta: 6
• Quanto vale [math]3^{4} \bmod 7[/math]? Risposta: 4

Esercizio 2 – Scomposizione dell’esponente

Calcola: [math]2^{50} \bmod 11[/math].

Soluzione

11 è primo e 2 non è multiplo di 11, quindi per Fermat:

[math]2^{10} \equiv 1 \pmod{11}.[/math]

Scriviamo [math]50 = 10 \cdot 5[/math]. Allora:

[math]\displaystyle \begin{aligned}
2^{50} &= (2^{10})^{5} \\
&\equiv 1^{5} \pmod{11} \\
&\equiv 1 \pmod{11}.
\end{aligned}[/math]

Risultato: [math]2^{50} \bmod 11 = 1[/math].

Mini‑quiz

• Perché possiamo ridurre l’esponente modulo 10? Risposta: perché [math]2^{10} \equiv 1[/math]
• Qual è il resto di [math]2^{50}[/math] diviso 11? Risposta: 1

Esercizio 3 – Uso della forma equivalente

Dimostra che [math]5^{7} \equiv 5 \pmod{7}[/math] usando la forma equivalente [math]a^{p} \equiv a \pmod{p}[/math].

Soluzione

La forma equivalente del teorema dice che per ogni intero [math]a[/math] e per ogni primo [math]p[/math] si ha

[math]a^{p} \equiv a \pmod{p}.[/math]

Qui [math]a = 5[/math] e [math]p = 7[/math]. Quindi direttamente:

[math]5^{7} \equiv 5 \pmod{7}.[/math]

Se vogliamo verificare:

[math]\displaystyle \begin{aligned}
5^{7} &= 78125, \\
78125 \div 7 &= 11160 \text{ con resto } 5,
\end{aligned}[/math]

quindi effettivamente [math]5^{7} \equiv 5 \pmod{7}[/math].

Mini‑quiz

• Quale forma del teorema si utilizza? Risposta: [math]a^{p} \equiv a \pmod{p}[/math]
• È necessario che [math]a[/math] non sia divisibile per [math]p[/math] in questa forma? Risposta: No, vale per ogni [math]a[/math] intero

Esercizio 4 – Potenza con esponente grande

Calcola: [math]7^{2024} \bmod 13[/math].

Soluzione

13 è primo, 7 non è divisibile per 13, quindi per Fermat:

[math]7^{12} \equiv 1 \pmod{13}.[/math]

Dividiamo 2024 per 12:

[math]\displaystyle \begin{aligned}
2024 &= 12 \cdot 168 + 8,
\end{aligned}[/math]

poiché [math]12 \cdot 168 = 2016[/math] e [math]2024 – 2016 = 8[/math]. Quindi

[math]\displaystyle \begin{aligned}
7^{2024} &= 7^{\,12 \cdot 168 + 8} \\
&= (7^{12})^{168} \cdot 7^{8} \\
&\equiv 1^{168} \cdot 7^{8} \pmod{13} \\
&\equiv 7^{8} \pmod{13}.
\end{aligned}[/math]

Calcoliamo ora [math]7^{8} \bmod 13[/math] per passi:

[math]\displaystyle \begin{aligned}
7^{2} &= 49 \equiv 10 \pmod{13}, \\
7^{4} &= (7^{2})^{2} \equiv 10^{2} = 100 \equiv 9 \pmod{13}, \\
7^{8} &= (7^{4})^{2} \equiv 9^{2} = 81 \equiv 3 \pmod{13}.
\end{aligned}[/math]

Pertanto:

[math]7^{2024} \equiv 3 \pmod{13}.[/math]

Mini‑quiz

• Qual è l’esponente ciclico modulo 13? Risposta: 12
• Quale resto si ottiene? Risposta: 3

Esercizio 5 – Riduzione con esponente negativo (inverso modulare)

Calcola: [math]2^{-7} \bmod 17[/math], ossia l’inverso di [math]2^{7}[/math] modulo 17.

Soluzione

Poiché 17 è primo e 2 non è divisibile per 17, Fermat dà

[math]2^{16} \equiv 1 \pmod{17}.[/math]

Scriviamo l’esponente negativo come differenza:

[math]\displaystyle \begin{aligned}
2^{-7} &\equiv 2^{16 – 7} \pmod{17} \\
&\equiv 2^{9} \pmod{17}.
\end{aligned}[/math]

Infatti [math]2^{-7} \cdot 2^{7} \equiv 1[/math], e moltiplicando per [math]2^{16}[/math] (che è 1) si ottiene [math]2^{9}[/math]. Ora calcoliamo [math]2^{9} \bmod 17[/math] per passi:

[math]\displaystyle \begin{aligned}
2^{4} &= 16 \equiv -1 \pmod{17}, \\
2^{8} &= (2^{4})^{2} \equiv (-1)^{2} = 1 \pmod{17}, \\
2^{9} &= 2^{8} \cdot 2 \equiv 1 \cdot 2 = 2 \pmod{17}.
\end{aligned}[/math]

Quindi

[math]2^{-7} \equiv 2 \pmod{17}.[/math]

Verifichiamo: [math]2^{7} = 128 \equiv 128 – 7 \cdot 17 = 128 – 119 = 9 \pmod{17}[/math]. L’inverso di 9 modulo 17 è 2, poiché [math]9 \cdot 2 = 18 \equiv 1 \pmod{17}[/math].

Mini‑quiz

• Come si trasforma un esponente negativo modulo [math]p-1[/math]? Risposta: si somma [math]p-1[/math] fino a ottenere un esponente positivo
• Qual è il risultato finale? Risposta: 2

Esercizio 6 – Combinazione di potenze e inversi

Calcola: [math]3^{100} \cdot 5^{-3} \bmod 19[/math].

Soluzione

19 è primo, 3 e 5 non sono divisibili per 19. Quindi:

[math]3^{18} \equiv 1 \pmod{19}, \qquad 5^{18} \equiv 1 \pmod{19}.[/math]

Riduciamo [math]3^{100}[/math]:

[math]\displaystyle \begin{aligned}
100 &= 18 \cdot 5 + 10, \\
3^{100} &= 3^{\,18 \cdot 5 + 10} \equiv 1^{5} \cdot 3^{10} \equiv 3^{10} \pmod{19}.
\end{aligned}[/math]

Per [math]5^{-3}[/math], usiamo [math]5^{18} \equiv 1[/math]:

[math]\displaystyle \begin{aligned}
5^{-3} &\equiv 5^{18 – 3} = 5^{15} \pmod{19}.
\end{aligned}[/math]

Quindi il prodotto diventa:

[math]3^{100} \cdot 5^{-3} \equiv 3^{10} \cdot 5^{15} \pmod{19}.[/math]

Ora calcoliamo i due termini separatamente. Per [math]3^{10} \bmod 19[/math]:

[math]\displaystyle \begin{aligned}
3^{2} &= 9, \\
3^{4} &= 9^{2} = 81 \equiv 81 – 4 \cdot 19 = 81 – 76 = 5 \pmod{19}, \\
3^{8} &= 5^{2} = 25 \equiv 6 \pmod{19}, \\
3^{10} &= 3^{8} \cdot 3^{2} \equiv 6 \cdot 9 = 54 \equiv 54 – 2 \cdot 19 = 16 \pmod{19}.
\end{aligned}[/math]

Per [math]5^{15} \bmod 19[/math], calcoliamo in modo efficiente:

[math]\displaystyle \begin{aligned}
5^{2} &= 25 \equiv 6 \pmod{19}, \\
5^{4} &= 6^{2} = 36 \equiv 36 – 1 \cdot 19 = 17 \equiv -2 \pmod{19}, \\
5^{8} &= (-2)^{2} = 4 \pmod{19}, \\
5^{15} &= 5^{8} \cdot 5^{4} \cdot 5^{2} \cdot 5^{1} \\
&\equiv 4 \cdot 17 \cdot 6 \cdot 5 \pmod{19}.
\end{aligned}[/math]

Ora moltiplichiamo con attenzione:

[math]\displaystyle \begin{aligned}
4 \cdot 17 &= 68 \equiv 68 – 3 \cdot 19 = 68 – 57 = 11 \pmod{19}, \\
11 \cdot 6 &= 66 \equiv 66 – 3 \cdot 19 = 66 – 57 = 9 \pmod{19}, \\
9 \cdot 5 &= 45 \equiv 45 – 2 \cdot 19 = 45 – 38 = 7 \pmod{19}.
\end{aligned}[/math]

Quindi [math]5^{15} \equiv 7 \pmod{19}[/math].

Infine:

[math]\displaystyle \begin{aligned}
3^{100} \cdot 5^{-3} &\equiv 16 \cdot 7 \pmod{19} \\
&\equiv 112 \pmod{19}.
\end{aligned}[/math]

Poiché [math]19 \cdot 5 = 95[/math] e [math]112 – 95 = 17[/math], si ha:

[math]3^{100} \cdot 5^{-3} \equiv 17 \pmod{19}.[/math]

Mini‑quiz

• Quali esponenti ciclici si utilizzano? Risposta: 18 per entrambe le basi
• Quanto vale [math]3^{10} \bmod 19[/math]? Risposta: 16
• Quanto vale [math]5^{-3} \bmod 19[/math]? Risposta: [math]5^{15} \equiv 7[/math]
• Risultato finale? Risposta: 17

risultato = (7 ** 2024) % 13

def fast_mod_exp(base, exp, mod):
    """
    Calcola (base^exp) % mod in tempo logaritmico O(log exp).
    Gestisce anche gli esponenti negativi assumendo che 'mod' sia un numero primo.
    """
    # Gestione dell'edge case: esponente negativo (Inverso Modulare)
    if exp < 0:
        # Applichiamo Fermat (a^(p-2) mod p) per trovare l'inverso della base.
        # Richiamiamo la funzione stessa invertendo i parametri.
        base = fast_mod_exp(base, mod - 2, mod)
        exp = -exp  # Rende l'esponente positivo per procedere col calcolo standard

    risultato = 1
    base = base % mod
    
    while exp > 0:
        # Se il bit meno significativo dell'esponente è 1, moltiplica
        if (exp % 2) == 1:
            risultato = (risultato * base) % mod
            
        # Quadra la base e dimezza l'esponente (shift a destra)
        base = (base * base) % mod
        exp = exp // 2
        
    return risultato

# Test con l'esercizio 5 dell'articolo: l'inverso di 2^7 mod 17
print(fast_mod_exp(2, -7, 17))