Seção 26

Aritmética modular

intermediárioviz

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

Define igualdade de restos módulo n.

intermediárioviz

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

As congruências são preservadas sob adição e multiplicação.

intermediárioviz

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

O inverso existe exatamente quando a e n são primos.

intermediário

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

Conecta o máximo divisor comum com combinações lineares inteiras.

avançadoviz

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

Sistemas com módulos coprimos pareados têm uma solução única módulo N.

avançadoviz

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

Resultado central para aritmética modular e criptografia.