Inicio / Teoria dos numeros / Congruencias e restos
Trilha 2

Congruencias e restos

Esta trilha organiza a linguagem modular: quando dois numeros deixam o mesmo resto, eles passam a se comportar do mesmo modo modulo n.

Congruencias

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

Definicao
a ≡ b (mod n)  ⇔  n | (a-b)
!
Leitura pratica: modulo n significa que voce olha para os numeros como classes de restos: 0, 1, 2, ..., n-1.

Operacoes modulo n

Voce pode somar, subtrair e multiplicar congruencias sem medo. Isso e o que torna a aritmetica modular tao poderosa em contas grandes.

SeEntao
a ≡ b e c ≡ da+c ≡ b+d
mesmas hipotesesa-c ≡ b-d
mesmas hipotesesac ≡ bd
Cuidado: divisao modulo n pede mais cuidado. Em geral, voce so pode simplificar quando o fator que sai e inversivel modulo n.

Inverso modular

O inverso modular de a modulo n e um numero u tal que au ≡ 1 (mod n). Ele permite "dividir" em congruencias quando existe.

Criterio de existencia
a tem inverso modulo n  ⇔  mdc(a,n)=1

Esse criterio e profundamente ligado a Bezout: se ax + ny = 1, entao x ja e um inverso de a modulo n.

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

Ciclos e potencias

Ultimo algarismo e resto de potencias grandes quase sempre se resolvem enxergando o ciclo modular.

Exemplo
Qual e o ultimo algarismo de 7202?
1
Modulo 10, as potencias 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 ultimo algarismo e 9.

Exponenciacao modular

Quando o expoente cresce muito, nao vale expandir. O caminho certo e reduzir a base modulo n, procurar ciclos ou quebrar o expoente em potencias de 2.

!
Roteiro pratico: primeiro reduza a base, depois procure periodicidade; se o modulo 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 periodo e 3.
2
Como 100 ≡ 1 (mod 3), usamos o primeiro termo do ciclo.
2100 ≡ 2 (mod 7).

Leitura de restos

Muitos problemas nao pedem a conta completa, mas apenas o resto. Nesses casos, vale a pena reduzir logo os numeros grandes antes de operar.

Ideia central
Substitua numeros grandes por restos pequenos equivalentes antes de multiplicar ou elevar.

Por exemplo, se 43 ≡ 1 (mod 7), entao 435 ≡ 15 ≡ 1 (mod 7).

Sistemas de congruencias

As vezes o problema fornece varios restos ao mesmo tempo. Quando os modulos sao coprimos dois a dois, o Teorema Chines dos Restos garante uma unica solucao modulo o produto deles.

Teorema chines dos restos
Se m e n sao coprimos, o sistema x ≡ a (mod m), x ≡ b (mod n) tem solucao unica modulo mn
Exemplo
Resolva o sistema x ≡ 1 (mod 3) e x ≡ 2 (mod 5).
1
Liste numeros congruentes a 1 modulo 3: 1, 4, 7, 10, ...
2
O primeiro que deixa resto 2 na divisao por 5 e 7.
A solucao e x ≡ 7 (mod 15).

Exercicio rapido

Cheque rapido
Se mdc(a,n)=1, o que isso garante em aritmetica modular?
← Anterior Divisibilidade e primos