Aritmetica modulare - somma, prodotto, potenza

La congruenza si comporta bene rispetto alle operazioni: si può “ridurre modulo $n$” in qualsiasi momento del calcolo, il che rende praticabili anche potenze altrimenti enormi.

Proprietà — Compatibilità con le operazioni

Se $a\equiv a'\pmod n$ e $b\equiv b'\pmod n$, allora $a+b \equiv a'+b'\pmod n, \quad a\cdot b\equiv a'\cdot b'\pmod n, \quad a^k\equiv (a')^k\pmod n.$ L’aritmetica modulare “rispetta” le operazioni di somma, prodotto e potenza. Non sempre la divisione: $2x\equiv 4\pmod 6$ non implica $x\equiv 2$ (anche $x=5$ funziona). La divisione modulare richiede che $\mathrm{mcd}(a,n)=1$.

Esempio — Calcolo veloce di potenze modulari

$7^{100}\pmod{13}$. Per Fermat $7^{12}\equiv 1\pmod{13}$. Allora $7^{100} = 7^{96}\cdot 7^4 = (7^{12})^8\cdot 7^4\equiv 7^4 = 2401 = 13\cdot 184 + 9\equiv 9\pmod{13}.$

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Congruenza
Metodi: Aritmetica modulare
Competenze: Calcolare · Usare formule