Sezione 26

Aritmetica modulare

intermedioviz

a \equiv b (mod n) ⟺ n ∣ (a - b)

Definisce l'uguaglianza dei residui modulo n.

intermedioviz

a \equiv b, c \equiv d (mod n) \Rightarrow a + c \equiv b + d, a c \equiv b d (mod n)

Le congruenze sono conservate sotto somma e prodotto.

intermedioviz

a a^{- 1} \equiv 1 (mod n) ⟺ g cd (a, n) = 1

Il contrario esiste esattamente quando a e n sono coprimi.

intermedio

a x + b y = g cd (a, b)

Connetti il massimo comun divisore con combinazioni lineari intere.

avanzatoviz

x \equiv a_{i} (mod n_{i}); N = i \prod n_{i}

I sistemi con moduli coprimi hanno una soluzione unica modulo N.

avanzatoviz

a^{p - 1} \equiv 1 (mod p) (p ∤ a)

Risultato centrale per l'aritmetica modulare e la crittografia.