Lista4-Teoria dos Números_2013-gabarito

Prévia do material em texto

Estruturas Discretas – Lista de Exercícios – Teoria dos Números 
Profa. Heloisa – 2º. Sem. 2013 - gabarito 
 
1) Para os pares de inteiros a e b a seguir, determine q e r tais que a = qb + r e 0  r < b. 
a) a = 100, b = 3. 
100=3*33 + 1 q=33 r=1 
b) a = -100, b = 3. 
-100= -34*3 + 2 q = -34 r = 2 
c) a = 99, b = 3. 
99 = 33*3 q = 33 r = 0 
d) a = -99, b = 3. 
-99 = -33*3 q = -33 r = 0 
e) a = 0, b = 3. 
0 = 0*3 + 0 q = 0 r = 0 
 
2) Para cada par de inteiros a e b do exercício anterior, calcule a div b e a mod b. 
 
3) Calcule: 
a) mdc(20,25). 
Iniciamos com a = 20 e b = 25 
Calculamos c = 20 mod 25 = 20 
Como 20 é diferente de 0, devemos calcular mdc(25, 20) 
 
Reiniciamos o processo com a = 25 e b = 20 
Calculamos c = 25 mod 20 = 5 
Como 5 é diferente de 0, devemos calcular mdc(20, 5) 
 
Reiniciamos o processo com a = 20 e b = 5 
Calculamos c = 20 mod 5 = 0 
Como obtemos c=0, obtemos a resposta mdc(20,5) = 5. 
Portanto, mdc(20, 5) = mdc(25, 20) = 5. 
 
b) mdc(123, 23). 
Iniciamos com a = 123 e b = 23 
Calculamos c = 123 mod 23 = 8 
Como 8 é diferente de 0, devemos calcular mdc(23, 8) 
 
Reiniciamos o processo com a = 23 e b = 8 
Calculamos c = 23 mod 8 = 7 
Como 7 é diferente de 0, devemos calcular mdc(8, 7) 
 
Reiniciamos o processo com a = 8 e b = 7 
Calculamos c = 8 mod 7 = 1 
Como 1 é diferente de 0, devemos calcular mdc(7, 1) 
 
Reiniciamos o processo com a = 7 e b = 1 
Calculamos c = 7 mod 1 = 0 
Como obtemos c=0, obtemos a resposta mdc(7,1) = 1. 
Portanto, mdc(7, 1) = mdc(8, 7) = mdc(23, 8) = mdc(123,23) = 1. 
 
c) mdc(89, 98). 
Iniciamos com a = 89 e b = 98 
Calculamos c = 89 mod 98 = 89 
Como 89 é diferente de 0, devemos calcular mdc(98, 89) 
 
Reiniciamos o processo com a = 98 e b = 89 
Calculamos c = 98 mod 89 = 9 
Como 9 é diferente de 0, devemos calcular mdc(89, 9) 
 
Reiniciamos o processo com a = 89 e b = 9 
Calculamos c = 89 mod 9 = 8 
Como 8 é diferente de 0, devemos calcular mdc(9, 8) 
 
Reiniciamos o processo com a = 9 e b = 8 
Calculamos c = 9 mod 8 = 1 
Como 1 é diferente de 0, devemos calcular mdc(8, 1) 
 
Reiniciamos o processo com a = 8 e b = 1 
Calculamos c = 8 mod 1 = 0 
Como obtemos c=0, obtemos a resposta mdc(8,1) = 1. 
Portanto, mdc(8, 1) = mdc(9, 8) = mdc(89, 9) = mdc(98, 89) = mdc(89,98) = 1. 
 
d) mdc(54995, 54). 
Iniciamos com a = 54995 e b = 54 
Calculamos c = 54995 mod 54 = 23 
Como 23 é diferente de 0, devemos calcular mdc(54, 23) 
 
Reiniciamos o processo com a = 54 e b = 23 
Calculamos c = 54 mod 23 = 8 
Como 8 é diferente de 0, devemos calcular mdc(23, 8) 
 
Reiniciamos o processo com a = 23 e b = 8 
Calculamos c = 23 mod 8 = 7 
Como 7 é diferente de 0, devemos calcular mdc(8, 7) 
 
Reiniciamos o processo com a = 8 e b = 7 
Calculamos c = 8 mod 7 = 1 
Como 1 é diferente de 0, devemos calcular mdc(7, 1) 
 
Reiniciamos o processo com a = 7 e b = 1 
Calculamos c = 7 mod 1 = 0 
Como obtemos c=0, obtemos a resposta mdc(7,1) = 1. 
Portanto, mdc(7, 1) = mdc(8, 7) = mdc(23, 8) = mdc(54, 23) = mdc(89,98) = 1. 
 
4) Para cada par de inteiros a, b do exercício anterior, determine os inteiros x e y tais que ax + 
by = mdc(a, b). 
 
a) mdc(20,25)=5. 
20 mod 25 = 20 e 20 div 25 = 0 
(Como esta primeira iteração apenas inverte a ordem dos valores de a e b, não tem utilidade 
no processo de retro substituição) 
 
25 mod 20 = 5 e 25 div 20 = 1 
20 mod 5 = 0 e 20 div 5 = 4 
 
Escrevendo na forma a = qb + r 
(I) 20 = 0*25 + 20 (esta equação não será usada) 
(II) 25 = 1*20 + 5 
(III) 20 = 4*5 + 0 
 
Isolando r 
(I) 20 = 20 - 0*25 
(II) 5 = 25 - 1*20 
(III) 0 = 20 - 4*5 
 
Utilizando a segunda equação que corresponde ao 5 (mdc entre 25 e 20) 
5 = 25 - 1*20 (não é necessário substituir o 20 da primeira equação) 
Logo, x=-1 e y=1 
 
b) mdc(123, 23)=1 
 
c) mdc(89, 98)=1 
 
89 mod 98 = 89 e 89 div 98 = 0 
(Como esta primeira iteração apenas inverte a ordem dos valores de a e b, não tem 
utilidade no processo de retro substituição) 
98 mod 89 = 9 e 98 div 89 = 1 
89 mod 9 = 8 e 89 div 9 = 9 
9 mod 8 = 1 e 9 div 8 = 1 
8 mod 1 = 0 e 8 div 1 = 8 
 
Escrevendo na forma a = qb + r 
 
(I) 89 = 0*98 + 89 (esta equação não será usada) 
(II) 98 = 1*89 + 9 
(III) 89 = 9*9 + 8 
(IV) 9 = 1*8 + 1 
(V) 8 = 8*1 + 0 
 
Isolando r 
 
(I) 89 = 89 - 0*98 
(II) 9 = 98 - 1*89 
(III) 8 = 89 - 9*9 
(IV) 1 = 9 - 1*8 
(V) 0 = 8 - 8*1 
 
Utilizando a equação IV: 
1 = 9 - 1*8 
 
Substituindo o 8 usando a equação III: 
1 = 9 - 1*8 
1 = 9 - 1*(89 - 9*9) 
1 = 9 -1*89 + 9*9 
1 = -1*89 + 10*9 
 
Substituindo o 9 usando a equação II: 
1 = -1*89 + 10*9 
1 = -1*89 + 10*(98 - 1*89) 
1 = -1*89 + 10*98 - 10*89 
1 = -11*89 + 10*98 
Logo, x=-11 e y=10 
 
d) mdc(54995, 54). 
 
5) Prove que, se a e b têm um máximo divisor comum, ele é único. 
Sejam a e b inteiros, não simultaneamente nulos. 
Vamos supor, por hipótese de contradição, que o máximo divisor comum de a e b não é 
único, ou seja, x e y são máximos divisores comuns de a e b e x  y. 
Se x é MDC de a e b, temos: 
i) x|a e x|b e 
ii) se z|a e z|b então z  x. (x é o máximo divisor comum) 
Logo, y  x. 
Analogamente, se y é MDC de a e b, temos: 
iii) y|a e y|b e 
iv) se z|a e z|b então z  y. (y é o máximo divisor comum) 
Logo, x  y. 
Assim, se y  x e x  y, x = y, o que contradiz a hipótese de que x  y. 
Logo, o MDC de a e b é único. 
 
6) Calcule o seguinte, no contexto Z10: 
a) 3  3 
3  3 = (3 + 3) mod 10 = 6 mod 10 = 6 
b) 6  6 
c) 7  3 
7  3 = (7 + 3) mod 10 = 10 mod 10 = 0 
d) 9  8 
9  8 = (9 + 8) mod 10 = 17 mod 10 = 7 
e) 3  3 
3  3 = (3 * 3) mod 10 = 9 mod 10 = 9 
f) 5  2 
g) 6  6 
h) 5 Ө 8 
5 Ө 8 = (5 - 8) mod 10 = -3 mod 10 = 7 
i) 8 Ө 5 
j) 8  7 
8  7 = 8  7-1 = 8  3 = (8 * 3) mod 10 = 24 mod 10 = 4 
k) 5  4 
Não está definido, pois 4 não tem inverso em Z10. 
 
7) Considerando os contextos Z7, Z12 e Z14., faça: 
a) Diga quais elementos em cada um desses contextos são invertíveis e por que; 
b) Encontre o inverso de todos os elementos (quando existir) em cada um desses contextos. 
 
Contexto Z7: 
São invertíveis os elementos: 1,2,3,4,5 e 6, porque são os elementos relativamente primos 
com 7. Os inversos são 1-1 = 1, 2-1 = 4, 3-1= 5 e 6-1 = 6. 
 
Contexto Z12: 
São invertíveis os elementos: 1, 5, 7 e 11, porque são os elementos relativamente primos 
com 12. Os inversos são 1-1 = 1, 5-1 = 5, 7-1 = 7, 11-1 = 11. 
 
Contexto Z14: 
São invertíveis os elementos: 1, 3, 5, 9, 11 e 13, porque são os elementos relativamente 
primos com 14. Os inversos são 1-1 = 1, 3-1 = 5, 9-1 = 11 e 13-1 = 13. 
 
8) Seja n um número inteiro com n  2. Prove que, em Zn, o elemento n-1 é seu próprio inverso. 
 
Para mostrar que n-1 é seu próprio inverso, devemos mostrar que 
(n-1)  (n-1) = 1 
(n-1) * (n-1) mod n = (n*n -2n +1) mod n = (n-2)n +1 mod n = 1 
((n-2)n é múltiplo de n) 
 
9) Resolva as equações no contexto indicado: 
a) 3  x = 4 em Z11 
 
Método 1: Testar todos os valores de x: 
x = 0: 3  0 = (3.0) mod 11 = 0 
x = 1: 3  1 = (3.1) mod 11 = 3 
x = 2: 3  2 = (3.2) mod 11 = 6 
x = 3: 3  3 = (3.3) mod 11 = 9 
x = 4: 3  4 = (3.4) mod 11 = 1 
x = 5: 3  5 = (3.5) mod 11 = 4 Solução: x = 5 
x = 6: 3  6 = (3.6) mod 11 = 7 
x = 7: 3  7 = (3.7) mod 11 = 10 
x = 8: 3  8 = (3.8) mod 11 = 2 
x = 9: 3  9 = (3.9) mod 11 = 5 
x = 10: 3  10 = (3.10) mod 11 = 8 
 
Método 2: 
Verificar se o coeficiente de x tem inverso no contexto 
3  4 = (3.4) mod 11 = 1, logo, o inverso de 3 é 4 em Z11 
 
Multiplicar os dois lados da equação pelo inverso de 3: 
3  x = 4 => 3-1  3  x = 3-1  4 => x = 3-1  4 => x = 4  4= (4.4) mod 11 = 5 
Solução: x = 5 
 
b) 4  x Ө 8 = 9 em Z11 
A ordem de prioridade dos operadores é a mesma da aritmética comum: 
4  x Ө 8 = 9 em Z11 
equivale a 
(4  x) Ө 8 = 9 em Z11 
Fazendo (4  x) = y, temos: 
y Ө 8 = 9, logo, y = 6 
Agora vamos resolver 4  x = 6. 
Como 4 tem inverso em Z11 e 4
-1 = 3, 
4  x = 6 => 3  4  x = 6  3 => x = 6  3 => x = 7 
Solução: x = 7. 
 
c) 3  x  8 = 1 em Z10 
 
A ordem de prioridade dos operadores é a mesma da aritmética comum: 
3  x  8 = 1 em Z10 
equivale a 
(3  x)  8 = 1 em Z10 
Fazendo (3  x) = y, temos: 
Se y  8 = 1, y = 3 
(Podemos calcular testando os valores de y ou calculando y = 1 Ө 8 = -7 mod 10 = 3) 
 
Logo, (3  x) = 3 
Podemos calcular usando um dos dois métodos: 
- testando todos os valores de x 
- Como 3 tem inverso em Z10 e 3
-1 = 7, usando a operação inversa: 
3  x = 3 => 3-1  3  x = 3-1  3 => x = 3-1  3 => x = 7  3 => x = (7.3) mod 10 = 1 
Solução: x = 1 
 
10) Resolva as equações no contexto indicado (pode haver mais de uma solução, ou nenhuma): 
a) 2  x = 4 em Z10 
Nesta equação não é possível aplicar o método 2 (multiplicar os dois lados da equação 
pelo inverso de 2), pois 2 não tem inverso em Z10. 
É preciso utilizar a estratégia de testar todos os valores de x. Pode haver mais de uma 
solução ou não haver solução alguma. 
x=0: 2  0 = (2.0) mod 10 = 0 
x=1: 2  1 = (2.1) mod 10 = 2 
x=2: 2  2 = (2.2) mod 10 = 4 
x=3: 2  3 = (2.3) mod 10 = 6 
x=4: 2  4 = (2.4) mod 10 = 8 
x=5: 2  5 = (2.5) mod 10 = 0 
x=6: 2  6 = (2.6) mod 10 = 2 
x=7: 2  7 = (2.7) mod 10 = 4 
x=8: 2  8 = (2.8) mod 10 = 6 
x=9: 2  9 = (2.9) mod 10 = 8 
As soluções são x=2 e x=7. 
 
b) 2  x = 3 em Z10 
Aproveitando a resolução do item anterior, verificamos que não há solução para a 
equação. 
 
c) 9  x = 4 em Z12 
Neste item, também não é possível aplicar o método de multiplicar os dois lados da 
equação pelo inverso do coeficiente do x, uma vez que 9 não tem inverso em Z12. 
Vamos resolver testando todos os valores de x. 
x=0: 9  0 = (9.0) mod 12 = 0 
x=1: 9  1 = (9.1) mod 12 = 9 
x=2: 9  2 = (9.2) mod 12 = 6 
x=3: 9  3 = (9.3) mod 12 = 3 
x=4: 9  4 = (9.4) mod 12 = 0 
x=5: 9  5 = (9.5) mod 12 = 9 
x=6: 9  6 = (9.6) mod 12 = 6 
x=7: 9  7 = (9.7) mod 12 = 3 
x=8: 9  8 = (9.8) mod 12 = 0 
x=9: 9  9 = (9.9) mod 12 = 9 
x=10: 9  10 = (9.10) mod 12 = 6 
x=11: 9  11 = (9.11) mod 12 = 3 
 
Logo, não há solução para a equação. 
 
11) Resolva as equações no contexto indicado (certifique-se de que achou todas as soluções): 
a) x  x = 1 em Z13 
Verificar os valores de x 
Se x = 0, 0  0 = 0 
Se x = 1, 1  1 = (1.1) mod 13 = 1 
Se x = 2, 2  2 = (2.2) mod 13 = 4 
Se x = 3, 3  3 = (3.3) mod 13 = 9 
Se x = 4, 4  4 = (4.4) mod 13 = 3 
Se x = 5, 5  5 = (5.5) mod 13 = 12 
Se x = 6, 6  6 = (6.6) mod 13 = 10 
Se x = 7, 7  7 = (7.7) mod 13 = 49 mod 13 = 10 
Se x = 8, 8  8 = (8.8) mod 13 = 64 mod 13 = 12 
Se x = 9, 9  9 = (9.9) mod 13 = 81 mod 13 = 3 
Se x = 10, 10  10 = (10.10) mod 13 = 100 mod 13 = 9 
Se x = 11, 11  11 = (11.11) mod 13 = 121 mod 13 = 4 
Se x = 12, 12  12 = (12.12) mod 13 = 144 mod 13 = 1 
 As soluções são x=1 e x=12. 
 
b) x  x = 11 em Z13 
Com base na solução do exercício anterior, verificamos que não há solução para a 
equação. 
 
c) x  x = 4 em Z15 
 
12) Ache a-1 em Zm onde: 
 
a) a = 37 e m = 249; 
O número 37 tem inverso em Z249 se mdc(249,37) = 1. 
Encontrar o mdc(249,37): 
Passo 1: a = 249, b = 37 
 c = a mod b = 249 mod 37 = 27 (27  0) 
Passo 2 : a = 37, b = 27 
 c = a mod b = 37 mod 27 = 10 (10  0) 
Passo 3 : a = 27, b = 10 
 c = a mod b = 27 mod 10 = 7 (7  0) 
Passo 4 : a = 10, b = 7 
 c = a mod b = 10 mod 7 = 3 (3  0) 
Passo 5 : a = 7, b = 3 
 c = a mod b = 7 mod 3 = 1 (1  0) 
Passo 6 : a = 3, b = 1 
 c = a mod b = 3 mod 1 = 0 . Aqui, c = 0, logo: mdc(3,1) = 1 
Temos: mdc(249,37) = mdc(37, 27) = mdc(27,10) = mdc(10,7) = mdc(7,3) = mdc(3,1) = 1. 
Logo, 37 tem inverso em Z249. 
 
Para encontrar o inverso de 37, precisamos encontrar x  Z249 tal que 
37y = 1 em Z249, ou 
(37 * y) mod 249 = 1 ou 
37y + 249x = 1 
 
Vamos procurar os inteiros x e y tal que 249x + 37y = 1. 
Pela aplicação do Algoritmo de Euclides, temos as equações: 
(I) 249 = 6*37+27 
(II) 37 = 1*27+10 
(III) 27 = 2*10+7 
(IV) 10 = 1*7+3 
(V) 7 = 2*3+1 
(VI) 3 = 1*3 +0 
 
Isolando o r: 
(I) 27 = 249 – 6*37 
(II) 10 = 37 – 1*27 
(III) 7 = 27 – 2*10 
(IV) 3 = 10 – 1*7 
(V) 1 = 7 – 2*3 
(VI) 0 = 3 – 1*3 
 
Usando a equação V: 
1 = 7 – 2*3 
Substituindo o 3 com a equação IV: 
1 = 7 – 2*(10 – 1*7) = 7 – 2*10 + 2*7 
1 = – 2*10 + 3*7 
Substituindo o 7 com a equação III: 
1 = – 2*10 + 3*(27 – 2*10) = -2*10 + 3*27 – 6*10 
1 = 3*27 – 8*10 
Substituindo o 10 com a equação II: 
1 = 3*27 – 8*(37 – 1*27) = 3*27 – 8*37 + 8*27 
1 = -8*37 + 11*27 
Substituindo o 27 com a equação I: 
1 = -8*37 + 11*(249 – 6*37) = -8*37 + 11*249 -66*37 
1 = 11*249 + (-74)*37 
Como (-74)*37 + 11*249 = 1, então (-74)*37 mod 249 = 1. 
Mas -74  Z249, então calculamos -74 mod 249 = 175. 
Assim, 37-1 = 175 em Z249. 
 
b) a = 15 e m = 234. 
 
13) Calcule: 
a) 30  29 em Z431. 
b) 126  37 em Z249. 
No exercício anterior vimos que o inverso de 37 em Z249 é 175. 
Assim, 
126  37 = 126  37-1 = 126  175 = (126*175) mod 249 = 22050 mod 249 = 138 
 
14) Prove: para todo a, b  Zn , (a Ө b)  (b Ө a) = 0. 
a Ө b = (a-b) mod n = (a-b) + k1n 
(b Ө a) = (b-a) mod n = (b-a) + k2n 
(a Ө b)  (b Ө a) = [(a-b) + k1n + (b-a) + k2n] mod n = (k1+k2)n mod n = 0 
 
15) Para alguns valores de n (por exemplo, n=5), é verdade que a  b = 0 acarreta a = 0 ou b = 0. 
Encontre mais dois valores de n  2 para os quais a implicação: 
a  b = 0  a = 0 ou b = 0 
é verdadeira em Zn. 
 
 Para n = 7: 
 0 1 2 3 4 5 6 
0 0 0 0 0 0 0 0 
1 0 1 2 3 4 5 6 
2 0 2 4 6 1 3 5 
3 0 3 6 2 5 1 4 
4 0 4 1 5 2 6 3 
5 0 5 3 1 6 4 2 
6 0 6 5 4 3 2 1