Teoria dos números e aritmética modular: exercícios com soluções passo a passo
Exercícios grátis de Teoria dos números e aritmética modular com diagramas, dicas e soluções completas resolvidas. Valores novos a cada vez, em três níveis: mdc e restos, inversos e congruências, potências modulares e RSA.
Exercício gratuitoFácil
Encontre 942 mod 11, o resto r com 0 ≤ r < 11.
a = 942n = 11
Resposta exata: um número inteiro, sem arredondar.
Como resolver exercícios de Teoria dos números e aritmética modular
Reduza antes todos os números módulo n; os restos ficam entre 0 e n − 1.
Para um mdc, divida repetidamente com o algoritmo de Euclides; o último resto não nulo é o mdc.
Para um inverso, execute o algoritmo estendido e guarde o coeficiente de a; some n se ele for negativo.
Resolva a·x ≡ b multiplicando por a⁻¹; combine duas congruências escrevendo x = r₁ + m₁k.
Para potências, escreva o expoente em binário e eleve ao quadrado repetidamente; no RSA, d = e⁻¹ mod φ(n) com φ(n) = (p − 1)(q − 1).
Erros comuns
Dar um resto negativo para um número negativo.
Parar o algoritmo de Euclides no primeiro resto.
Deixar o inverso negativo em vez de somar n.
Tomar o expoente RSA d módulo n em vez de φ(n).
Reduzir o expoente módulo p em vez de p − 1 com o teorema de Fermat.
Fórmulas principais
Divisão com resto
a = q·n + r, 0 ≤ r < n
Euclides
gcd(a, b) = gcd(b, a mod b)
Mínimo múltiplo comum
lcm(a, b) = a·b/gcd(a, b)
Inversa
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruência linear
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Função totiente de Euler
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Aprenda Teoria dos números e aritmética modular do zero
1Restos e congruências
Dividir a por n dá um quociente q e um resto r: a = q·n + r com 0 ≤ r < n. O resto é escrito a mod n. Para um número negativo, q também é negativo: −3 = −1·7 + 4, portanto −3 mod 7 = 4.
Dois números são congruentes módulo n, a ≡ b (mod n), quando deixam o mesmo resto, isto é, quando n divide a − b.
Os restos podem ser reduzidos a cada passo, o que mantém os números pequenos:
(a + b) mod n = ((a mod n) + (b mod n)) mod n, e o mesmo para a·b
Por exemplo, 47·58 mod 9: 47 ≡ 2 e 58 ≡ 4, portanto 47·58 ≡ 8 (mod 9).
Autoavaliação Quanto é −17 mod 5?
2
3
−2
−3
Resposta: 3. −17 = −4·5 + 3, então o resto é 3. A resposta 2 é 17 mod 5; um resto nunca é negativo.
2Algoritmo de Euclides
O máximo divisor comum mdc(a, b) é o maior número que divide ambos. O algoritmo de Euclides usa mdc(a, b) = mdc(b, a mod b):
Divida: a = q·b + r.
Substitua (a, b) por (b, r).
Repita até que o resto seja 0. O último resto não nulo é o mdc.
O mínimo múltiplo comum decorre disso: mmc(a, b) = a·b / mdc(a, b).
Autoavaliação Quanto é mdc(84, 36)?
12
252
4
6
Resposta: 12. 84 = 2·36 + 12 e 36 = 3·12 + 0, então o mdc é 12. 252 é o mínimo múltiplo comum, 84·36/12.
3Inversos e o algoritmo estendido
O inverso de a módulo n é o número x com a·x ≡ 1 (mod n). Ele existe exatamente quando mdc(a, n) = 1.
O algoritmo de Euclides estendido executa Euclides em (n, a) e guarda um coeficiente t para cada resto, de modo que todo resto r ≡ t·a (mod n). Comece com t = 0 para n e t = 1 para a; cada novo t é o t de duas linhas acima menos q vezes o t de uma linha acima. Quando o resto 1 aparece, seu t é o inverso.
Com o inverso, uma congruência a·x ≡ b (mod n) é resolvida por x ≡ a⁻¹·b. Quando d = mdc(a, n) é maior que 1, há d soluções se d divide b, e nenhuma caso contrário.
Duas congruências com módulos coprimos, x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂), têm exatamente uma solução módulo m₁·m₂ (o teorema chinês do resto). Escreva x = r₁ + m₁k e resolva para k.
A elevação ao quadrado repetida calcula aᵏ mod n rapidamente: escreva k em binário, encontre a, a², a⁴, a⁸, … mod n elevando ao quadrado e reduzindo, e multiplique as potências cujo bit é 1.
Pequeno teorema de Fermat: para um primo p que não divide a, aᵖ⁻¹ ≡ 1 (mod p). Assim, o expoente pode ser reduzido módulo p − 1.
O RSA constrói uma chave a partir de dois primos p e q:
n = p·q e φ(n) = (p − 1)(q − 1).
Escolha e com mdc(e, φ(n)) = 1; (n, e) é a chave pública.
Calcule d = e⁻¹ mod φ(n): a chave privada.
Cifre c = mᵉ mod n; decifre m = cᵈ mod n.
O φ(n) de Euler conta os números de 1 a n que são coprimos com n: φ(p) = p − 1 para um primo, φ(pᵏ) = pᵏ − pᵏ⁻¹, e φ é multiplicativa para fatores coprimos.
Autoavaliação Uma chave RSA usa p = 5, q = 11 e e = 3. Quanto é d?
13
27
37
3
Resposta: 27. φ(n) = 4·10 = 40, e 3·27 = 81 = 2·40 + 1, então d = 27. O inverso de 3 módulo n = 55 seria 37, mas d é tomado módulo φ(n).
5Erros comuns
Dar um resto negativo para um número negativo: −17 mod 5 é 3, não −2.
Parar Euclides no primeiro resto em vez do último não nulo.
Esquecer de somar n a um coeficiente negativo do algoritmo estendido.
Calcular o expoente RSA d módulo n em vez de módulo φ(n).
Reduzir um expoente módulo p em vez de p − 1 com o teorema de Fermat.
6Como são as questões de prova
Fácil: mdc e restos. Você executa o algoritmo de Euclides para um mdc ou mmc, encontra restos de números negativos e reduz somas e produtos módulo n.
Médio: inversos e congruências. Você encontra inversos modulares com o algoritmo estendido, resolve congruências lineares, combina duas congruências com o teorema chinês do resto e calcula o φ(n) de Euler.
Difícil: potências modulares e RSA. Você usa a elevação ao quadrado repetida e o teorema de Fermat, resolve congruências com várias soluções e encontra expoentes privados RSA, textos cifrados e mensagens decifradas.
Encontre (914·953) mod 11 sem calcular os números grandes: reduza primeiro.
n = 11
Calcule (914·953) mod 11
Mostrar dicas
(x·y) mod n = ((x mod n)·(y mod n)) mod n, e o mesmo vale para somas.
914 mod 11 = 1, 953 mod 11 = 7.
Reduza o produto dos restos módulo 11.
Mostrar a resposta e a solução passo a passo
Divisibilidade e restos: a mod n é o resto r com 0 ≤ r < n e a = q·n + r, também quando a é negativo. O algoritmo de Euclides encontra mdc(a, b) repetindo a = q·b + r e substituindo (a, b) por (b, r); o último resto não nulo é o mdc. Então mmc(a, b) = a·b/mdc(a, b). Os restos podem ser reduzidos a cada passo: (a + b) mod n e (a·b) mod n dependem apenas de a mod n e b mod n.
Reduza cada número
914 ≡ 1, 953 ≡ 7 (mod 11)
Combine
1·7 = 7 ≡ 7 (mod 11)
Resposta
(914·953) mod 11 = 7
Exemplo 2Média
Encontre a função totiente de Euler φ(637), o número de inteiros de 1 a 637 que são coprimos com 637.
n = 637 = 72·13
Calcule φ(637)
Mostrar dicas
Fatore n em primos: 637 = 72·13.
φ é multiplicativa para fatores coprimos, e φ(pᵏ) = pᵏ − pᵏ⁻¹.
φ(n) = n·∏(1 − 1/p).
Mostrar a resposta e a solução passo a passo
Inversos e congruências: a tem inverso módulo n exatamente quando mdc(a, n) = 1. O algoritmo de Euclides estendido escreve 1 = s·n + t·a, e então a⁻¹ ≡ t (mod n). Uma congruência a·x ≡ b (mod n) com mdc(a, n) = 1 tem a solução x ≡ a⁻¹·b. Duas congruências x ≡ r₁ (mod m₁) e x ≡ r₂ (mod m₂) com módulos coprimos têm uma solução módulo m₁·m₂ (teorema chinês do resto). O φ(n) de Euler conta os números de 1 a n que são coprimos com n: φ(n) = n·∏(1 − 1/p).
Fatores primos
637 = 72·13
Totiente
φ(637) = φ(49)·φ(13) = 42·12 = 504
Resposta
φ(637) = 504
Exemplo 3Difícil
Uma chave RSA usa p = 13, q = 37 e e = 23. Decifre o texto cifrado c = 225: encontre a mensagem m.
p = 13q = 37e = 23c = 225
Calcule m
Mostrar dicas
n = 481, φ(n) = 432.
d = e⁻¹ mod φ(n) = 263.
m = cd mod n = 225263 mod 481: use a elevação ao quadrado repetida.
Mostrar a resposta e a solução passo a passo
Potências modulares e RSA: calcule aᵏ mod n por elevação ao quadrado repetida: escreva k em binário, eleve ao quadrado, reduza a cada passo e multiplique as potências cujo bit é 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) para um primo p que não divide a, então o expoente pode ser reduzido módulo p − 1. RSA: escolha primos p e q, n = p·q e φ(n) = (p − 1)(q − 1); o expoente público e é coprimo com φ(n), e o expoente privado é d = e⁻¹ mod φ(n). Cifre com c = mᵉ mod n e decifre com m = cᵈ mod n.
Expoente privado
n = 481, φ(n) = 432
d = 23−1 mod 432 = 263
Decifre por elevação ao quadrado repetida
263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)
Mensagem
m = 361
verificação: 36123 mod 481 = 225
Resposta
m = 361
Perguntas e respostas
Teoria dos números e aritmética modular: o que é?
Dividir a por n dá um quociente q e um resto r: a = q·n + r com 0 ≤ r < n. O resto é escrito a mod n. Para um número negativo, q também é negativo: −3 = −1·7 + 4, portanto −3 mod 7 = 4.
Dois números são congruentes módulo n, a ≡ b (mod n), quando deixam o mesmo resto, isto é, quando n divide a − b.
Teoria dos números e aritmética modular: como resolver os exercícios passo a passo?
Reduza antes todos os números módulo n; os restos ficam entre 0 e n − 1.
Para um mdc, divida repetidamente com o algoritmo de Euclides; o último resto não nulo é o mdc.
Para um inverso, execute o algoritmo estendido e guarde o coeficiente de a; some n se ele for negativo.
Resolva a·x ≡ b multiplicando por a⁻¹; combine duas congruências escrevendo x = r₁ + m₁k.
Para potências, escreva o expoente em binário e eleve ao quadrado repetidamente; no RSA, d = e⁻¹ mod φ(n) com φ(n) = (p − 1)(q − 1).
Teoria dos números e aritmética modular: quais são os erros mais comuns?
Dar um resto negativo para um número negativo.
Parar o algoritmo de Euclides no primeiro resto.
Deixar o inverso negativo em vez de somar n.
Tomar o expoente RSA d módulo n em vez de φ(n).
Reduzir o expoente módulo p em vez de p − 1 com o teorema de Fermat.
Teoria dos números e aritmética modular: o que se pratica?
Fácil: mdc e restos
Média: inversos e congruências
Difícil: potências modulares e RSA
Cada exercício tem valores novos, então você aprende o método em vez de decorar uma resposta. Travou? Abra primeiro uma dica pequena, e a explicação completa só quando precisar.
Como a prática funciona
Cada exercício tem valores novos, então você aprende o método em vez de decorar uma resposta.
Travou? Abra primeiro uma dica pequena, e a explicação completa só quando precisar.
Seu progresso, seus erros e seus exercícios salvos ficam guardados, para você revisar antes da prova.