Aritmética modular

Aritmética modular

Dois inteiros são congruentes módulo n quando têm o mesmo resto na divisão por n: a ≡ b (mod n) significa que n divide a − b. É a aritmética do relógio: 15 horas depois de 9h é 0h, porque 9 + 15 = 24 ≡ 0 (mod 12).

Relógio

A aba relógio mostra os resíduos de 0 a n − 1 em um círculo. O ponteiro parte de um início e avança k passos, dando o resíduo final (início + k) mod n.

Tabuada mod n

A tabela de multiplicação módulo n mostra (i · j) mod n. Algumas linhas repetem valores: isso acontece quando i tem fator em comum com n. Um elemento tem inverso exatamente quando o 1 aparece na linha dele: é a forma visual de mdc(a, n) = 1.

Congruência linear

Para resolver a·x ≡ b (mod n), calcule g = mdc(a, n):

• se g não divide b, não há solução;
• se g divide b, há exatamente g soluções módulo n. Divida tudo por g, ache o inverso de a/g módulo n/g e some múltiplos de n/g.

Por exemplo, em 6x ≡ 4 (mod 10), g = 2 divide 4, então há duas soluções: 4 e 9.

Inverso modular

O inverso de a módulo n é um x com a·x ≡ 1 (mod n). Ele existe exatamente quando mdc(a, n) = 1. O Euclides estendido (identidade de Bézout) dá o x.

Teorema Chinês do Resto

Um sistema x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂), ... tem solução única módulo o mmc dos módulos quando os módulos são coprimos dois a dois. Quando não são coprimos, o sistema pode ser incompatível: a ferramenta junta as congruências duas a duas e aponta a que se contradiz.

Entradas

Use inteiros. Módulos precisam ser positivos. Campos vazios e textos recebem mensagem.