Início / Teoria dos números / Congruências e restos
Trilha 1

Congruências e aritmética modular

Esta é a entrada natural da teoria dos números: quando dois números deixam o mesmo resto, eles passam a se comportar do mesmo modo módulo n.

Congruências

Dizer que a ≡ b (mod n) significa que a e b deixam o mesmo resto na divisão por n. Em outras palavras, n divide a-b.

Definição
a ≡ b (mod n)  ⇔  n | (a-b)
!
Leitura prática: módulo n significa que você olha para os números como classes de restos: 0, 1, 2, ..., n-1.

Operações módulo n

Você pode somar, subtrair e multiplicar congruências sem medo. Isso é o que torna a aritmética modular tão poderosa em contas grandes.

SeEntão
a ≡ b e c ≡ da+c ≡ b+d
mesmas hipótesesa-c ≡ b-d
mesmas hipótesesac ≡ bd
Cuidado: divisão módulo n pede mais cuidado. Em geral, você só pode simplificar quando o fator que sai é inversível módulo n.

Inverso modular

O inverso modular de a módulo n é um número u tal que au ≡ 1 (mod n). Ele permite "dividir" em congruências quando existe.

Critério de existência
a tem inverso módulo n  ⇔  mdc(a,n)=1

Esse critério é profundamente ligado a Bézout: se ax + ny = 1, então x já é um inverso de a módulo n.

Exemplo
Qual é o inverso de 3 módulo 7?
1
Teste produtos pequenos: 3.5 = 15.
2
Como 15 ≡ 1 (mod 7), o inverso é 5.
3-1 ≡ 5 (mod 7).

Ciclos e potências

Último algarismo e resto de potências grandes quase sempre se resolvem enxergando o ciclo modular.

Exemplo
Qual é o último algarismo de 7202?
1
Módulo 10, as potências de 7 repetem: 7, 9, 3, 1.
2
O ciclo tem tamanho 4. Como 202 ≡ 2 (mod 4), olhamos o segundo termo do ciclo.
O último algarismo é 9.

Exponenciação modular

Quando o expoente cresce muito, não vale expandir. O caminho certo é reduzir a base módulo n, procurar ciclos ou quebrar o expoente em potências de 2.

!
Roteiro prático: primeiro reduza a base, depois procure periodicidade; se o módulo for primo ou coprimo com a base, Fermat e Euler podem encurtar bastante o expoente.
Exemplo
Calcule 2100 (mod 7).
1
Veja o ciclo: 2, 4, 1. O período é 3.
2
Como 100 ≡ 1 (mod 3), usamos o primeiro termo do ciclo.
2100 ≡ 2 (mod 7).

Leitura de restos

Muitos problemas não pedem a conta completa, mas apenas o resto. Nesses casos, vale a pena reduzir logo os números grandes antes de operar.

Ideia central
Substitua números grandes por restos pequenos equivalentes antes de multiplicar ou elevar.

Por exemplo, se 43 ≡ 1 (mod 7), então 435 ≡ 15 ≡ 1 (mod 7).

Sistemas de congruências

Às vezes o problema fornece vários restos ao mesmo tempo. Quando os módulos são coprimos dois a dois, o Teorema Chinês dos Restos garante uma única solução módulo o produto deles.

Teorema chinês dos restos
Se m e n são coprimos, o sistema x ≡ a (mod m), x ≡ b (mod n) tem solução única módulo mn
Exemplo
Resolva o sistema x ≡ 1 (mod 3) e x ≡ 2 (mod 5).
1
Liste números congruentes a 1 módulo 3: 1, 4, 7, 10, ...
2
O primeiro que deixa resto 2 na divisão por 5 é 7.
A solução é x ≡ 7 (mod 15).

Exercícios rápidos

Cheque rápido
Se mdc(a,n)=1, o que isso garante em aritmética modular?
← Voltar Visão geral da matéria