Sección 26

Aritmética modular

intermedioviz

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

Define igualdad de residuos módulo n.

intermedioviz

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

Congruencias se preservan bajo suma y producto.

intermedioviz

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

El inverso existe exactamente cuando a y n son coprimos.

intermedio

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

Conecta el máximo común divisor con combinaciones lineales enteras.

avanzadoviz

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

Sistemas con módulos coprimos tienen solución única módulo N.

avanzadoviz

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

Resultado central para aritmética modular y criptografía.