Exercicios Resolvidos Aritmetica modular

Prévia do material em texto

Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA
Aritmética dos Restos
Contato: nibblediego@gmail.com
Escrito por Diego Oliveira - Publicado em 04/09/2016 - Atualizado em 21/04/2018
O que eu preciso saber?
Dizemos que dois inteiros  e b são congruentes módulo m se m | (−b). E escrevemos:
 ≡ b (mod m)
por exemplo:
16 ≡ 1 (mod 5), pois 5 | (16 − 1).
21 ≡ 16 (mod 5), pois 5 | (21 − 16).
Uma pequena observação!
Não é muito comum, em livros de álgebra ou de teoria dos números, trabalhar com
números negativos dentro desse conteúdo. Mas isso não quer dizer que eles não existam.
Por exemplo:
16 − (−4) = 20 e 10|20 ⇒ 16 ≡ −4 (mod 10).
Lembre-se dessa informação, pois as vezes trabalhar com números negativos pode fa-
cilitar a resolução de certos problemas.
Exemplo 1: Ache os restos das seguintes
divisões:
a) 245 por 7
b) 11100 por 100
c) 310 · 425 + 68 por 5
d) 52 · 4841 + 285 por 3
Solução de A:
Se 23 ≡ 1 (mod 7), então:
(23)15 ≡ 115 (mod 7)
⇒ 245 ≡ 1 (mod 7)
Ou seja, o resto de 245 por 7 é 1.
Solução de B:
Se 112 ≡ 21 (mod 100) então:
(112)50 ≡ 2150 mod(100).
Como 212 ≡ 41 (mod 100) então:
(212)25 ≡ 4125 (mod 100)
⇒ 2150 ≡ 4125 (mod 100).
Como 41 é um numero de dois dígitos e
termina com 1 é fácil concluir que 4125 ≡ 1
(mod 100).
Sendo assim:
(112)50 ≡ 2150 ≡ 4125 ≡ 1 (mod 100)
⇒ 11100 ≡ 1 (mod 100)
portanto, o resto da divisão citada é 1.
Solução de C:
Se 32 ≡ 4 (mod 5) então:
(32)5 ≡ 45 (mod 5)
310 ≡ 45 (mod 5) ()
Sabe-se que 40 é divisível por 5, então 42
≡ 2 (mod 5) ()
1
Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA
Como 62 ≡ 1 (modulo 5) então:
(62)4 ≡ 14 (mod 5)
⇒ 68 ≡ 1 (mod 5) ()
Usando (), () e ()
310 · 425 + 68 ≡ 4 · (2)5 + 1 = 129
⇒ 129 ≡ 4 (mod 5)
Ou seja, o resto da divisão solicitada é 4.
Solução de D:
Facilmente se conclui que 52 ≡ 1 (mod
3). Fazendo a divisão de 4841 por 3 encon-
tramos 2 como resto dessa divisão
4841
3
= 1613(3) + 2
Também sabe-se que 28 ≡ 1 (mod 3), por-
tanto 285 ≡ 1 (mod 3). Sendo assim:
52 · 4841 + 285 ≡ 1 · 2 + 1 (mod 3) ≡ 3
mod(3) ≡ 0 (mod 3).
Ou seja, o resto da divisão solicitada é 0.
Exemplo 2: Mostre que o numero 220−1
é divisível por 41
Solução:
25 ≡ −9 mod(41)
⇒ (25)4 ≡ (−9)4 mod(41)
⇒ 220 ≡ (−9)4 mod(41).
Como −94 = 6561 e a divisão de 6561
por 41 tem resto 1 então:
220 ≡ 1 mod(41)
Sendo assim, 220 − 1 ≡ 1 − 1 = 0
O que implica em 220 − 1 mod(41).
Como se queria demonstrar.
Exemplo 3: Qual é o resto da divisão eu-
clidiana de 15+ 25+ 35+ ...+ 995+ 1005 por
4? Justifique.
Sugestão: Dividir a soma dada em 25 gru-
pos de 4 parcelas.
Solução:
No módulo 4 a soma pode ser escrita as-
sim:
15+25+35+05+15+25+35+05+· · ·+15+25+35+05
Como a ordem dos fatores não altera o
resultado da soma em R, então podemos
deslocar o último termo da soma (05) para
agrupa-la em grupos de 4 termos.
(05+15+25+35)+ (05+15+25+35)+ · · ·
+(05 + 15 + 25 + 35)
Dividindo 100 por 4 o resultado será 25.
Então, concluí-se que existam 25 grupos de
quatro termos na soma acima. Isto é:
(05+15+25+35)+ (05+15+25+35)+ · · ·
+(05+15+25+35) = 25×(05+15+25+35)
= 25 × (1 + 32 + 243)
= 25 × (276)
Como 276 ≡ 0 no módulo 4 então:
25 × (276) = 25 × 0 = 0
⇒ 15 + 25 + · · · + 995 + 1005 ≡ 0 (mod 4).
Ou seja, o resto é zero.
Exemplo 4:
a) Mostre que o resto da divisão de um
numero por 10 é seu algarismo das unidades
e que o resto da divisão por 100 é o numero
formado pelo dois últimos algarismos do nu-
mero dado.
b) Ache o algarismo das unidades de
7(7
100).
c) Ache os dois últimos algarismos de
9(9
9).
2
Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA
Solução de A:
Seja n um número qualquer se n < 10 en-
tão a demonstração é evidente.
Se n > 10 então existe um q e p ∈ Z onde
pelo teorema da divisão euclidiana pode-se
afirmar que n = 10q + p com 10 > p > 0.
O que implica em n ≡ p (mod 10). Em out-
ras palavras a divisão de n por 10 é igual a
p que como é menor que dez é o algarismo
que representa a unidade (ou o último algar-
ismo do número dado).
Analogamente se prova para n negativo.
Solução de B:
Considere a seguinte sequência:
70 = 1 número terminado em 1.
71 = 7 número terminado em 7.
72 = 49 número terminado em 9.
73 = 343 número terminado em 3.
74 = 2401 número terminado em 1.
75 = 16807 número terminado em 7.
...
se continuássemos com ela perce-
beríamos que o final dos demais números
ainda seria, e na ordem, os números 1, 7, 9
e 3 até o fim.
Como as potências de 7 seguem esse
padrão e têm somente 4 algarismos difer-
entes para compor seu algarismo das
unidades (1, 3, 7 e 9), então podemos de-
terminar o número p tal que:
77
100 ≡ p (mod. 4)
pois com base nele facilmente descobri-
mos qual o algarismo das unidades. Veja:
Como 7 ≡ 3 (mod 4) e 100 ≡ 0 (mod 4)
então,
77
100 ≡ 330 (mod. 4)
⇒ 77100 ≡ 31 (mod. 4)
⇒ 77100 ≡ 3 (mod. 4).
Então, o algarismo da unidade de 77
100
é
3.
Solução de C:
Esse método pode ser aplicado sempre
que se desejar encontrar os dois últimos al-
garismos de um numero nn
n
(com n ∈ N).
É Primeiro determina-se um in-
teiro r tal que 99 ≡ r (mod 10).
99 =
�
93
�3 = (729)3
como 729 ≡ 9 no mó-
dulo 10 então:
99 ≡ 93 (mod 10)
⇒ 99 ≡ 729 (mod 10)
⇒ 99 ≡ 9 (mod 10)
⇒ r = 9
É Finalmente determinamos um
inteiro p tal que 9r ≡ p (mod 100).
99 = (93)3 = (729)3 ≡
(29)3 (mod 100)
Como 293 = 24389
então (29)3 ≡ 89 (mod
100). O que implica em
p = 89.
Sendo assim, os dois últimos
dígitos de 99
9
é 89.
3
Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA
Este trabalho está licenciado com uma
Licença Creative Commons -
Atribuição-NãoComercial-
CompartilhaIgual 4.0 Internacional.
Esse documento está sujeito a constante atualização ou mesmo correções, por isso,
certifique se que o que você têm em mãos é de fato a última versão do mesmo. Para
saber, bem como ter acesso a vários outros exercícios resolvidos de matemática, acesse:
www.number.890m.com
E se alguma passagem ficou obscura ou se algum erro foi cometido por favor entre em
contato para que possa ser feito a devida correção.
nbbedego@gm.com
.ƒcebook.com/theNmberType
.nmber.890m.com
4
http://creativecommons.org/licenses/by-nc-sa/4.0/