Exercicios Teoria Elementar dos Numeros 79

Prévia do material em texto

(a) 89 | 244 – 1. 
Solução: Se 89 | 244 – 1 então, 244 - 1 = 89.m  244 = 89m + 1. Portanto, 
devemos provar que 244  1 (mod. 89). 
A potencia inteira de dois imediatamente maior que 89 é 128 = 27 e 128 = 89.1 + 
39  39 (mod.89) 
27 x 27 = 214  39 x 39 = 1521 = 17.89 + 8  8 
244 = 214 x 214 x 214 x22  8 x 8 x 8 x 4 = 128 x 16  39 x 16 = 624 = 89.7 + 1  
1 (mod. 89). 
Portanto, 244  1 (mod.89) 
(b) 97 | (248 – 1) 
Solução: Conforme item anterior, devemos provar que 248  1 (mod. 97) 
Tomemos a potência 29 = 512 = 5.97 + 27  27 (mod. 97) 
218 = 29 x 29 
 27 x 27 = 729 = 7 x 97 + 50  50 (mod. 97) 
236 = 218 x 218  50 x 50 = 2500 = 25.97 + 75  75 (mod. 97) 
248 = 236 x 29 x 23  75 x 27 x 8  75 x 216  75 x ( 97.2 + 22)  75 x 22 = 1650 
= 97.17 + 1  1 (mod. 97). 
Portanto, 248  1 (mod. 97) ou 97 | 248 - 1 . 
 
16 – Demonstrar que, se a  b (mod. m) então mdc(a, m) = mdc(b, m). 
Solução: Se a  b (mod. m) então a = xm + r e b = ym + r. 
Para r = 0, m é um divisor de a  mdc(a, m) = m. 
Da mesma forma, m é um divisor de b  mdc(b, m) = m. 
Assim, concluímos que mdc(a, m) = m = mdc(b, m). 
Para r  0, mdc(a, m) = mdc(m, r) e mdc(b, m) = mdc(m, r) de acordo com o 
algoritmo de Euclides ou processo das divisões sucessivas. 
Assim, mdc(a, m) = mdc(m, r ) = mdc(b, m). 
 
17 – Mostrar, mediante um exemplo, que ak  bk (mod. m) e k  j não implica aj  
bj. 
Solução: 82  62 (mod. 7) pois 82 = 64 = 7.9 + 1 e 62 = 36 = 5.7 + 1 e 2  9 
(mod. 7) 
89 = 82. 82. 82. 82.8  1.1.1.(7.1 + 1)  1.1.1.1 1 
69 = 62.62.62.62.6  1.1.1.6  6 que não congruente com 89. 
 
18 – Demonstrar as seguintes proposições: 
(a) Se a é um inteiro ímpar então a2  1 (mod. 8) 
Solução: Todos os inteiros são de uma das formas, 4k, 4k + 1, 4k + 2 ou 4k + 3. 
Serão ímpares as formas 4k + 1 e 4k + 3. 
Assim, a2 = (4k + 1)2 = 16k2 + 8k + 1 = 8(2k2 + k) + 1 = 8n + 1  1 (mod. 8) 
a2 = (4k + 3)2 = 16k2 + 24k + 9 = 16k2 + 24k + 8 + 1 = 8(2k2 + 3k + 1) + 1  1 
(mod. 8) 
(b) Se a é um inteiro qualquer, então a3 
 0, 1 ou 8 (mod. 9). 
Solução:- Todo número inteiro tem a forma: 3n, 3n + 1 ou 3n + 2. Para os seus 
cubos, temos: