Potenza modulare con Fermat

Testo

Calcola $2^{30}\bmod 31$ usando il piccolo teorema di Fermat.

Soluzione

$31$ è primo e $\mathrm{mcd}(2,31)=1$, quindi il piccolo teorema di Fermat dà $2^{31-1} = 2^{30} \equiv \boxed{1} \pmod{31}.$ Il risultato è immediato: l’esponente $30 = p-1$ è esattamente quello per cui il teorema garantisce il valore $1$.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare
Metodi: Aritmetica modulare
Competenze: Calcolare
Persone: Pierre de Fermat
Tipo di esercizio: Calcolo espressioni