Resolução Teoria dos Numeros Plinio Cap 2

Teoria dos Números  Capítulo 2 (Exercícios) 
 
1. Mostrar que 47 | 223  1. 
Para mostrar que 47 | 2
23
  1, devemos mostrar que 2
23
 ≡ 1 (mod 47). 
Notemos que 2
10
 = 1024 = 37 + 47  21. Ou seja, 2
10
 ≡ 37 (mod 47) ⇒ 210 ≡ 10 (mod 47). 
Então, [2
10
]
2 
≡ (10)
2
 (mod 47) ⇒ 220 ≡ 100 (mod 47) ⇒ 220 ≡ 6 (mod 47) (I) 
Vejamos, agora, que 2
3
 = 8 = 47  39, ou seja, 2
3
 ≡ 39 (mod 47) (II). 
De (I) e (II), (2
20
  2
3
) ≡ 6  (39) (mod 47) ⇒ 223 ≡ 234 (mod 47). 
Mas, 234 = 1  47  5, então 2
23
 ≡ 1 (mod 47). 
 ∎ 
 
2. Encontrar o resto da divisão de 734 por 51 e o resto da divisão de 563 por 29. 
i) Vejamos que 7
2
 ≡ 2 (mod 51). Então, (7
2
)
17
 ≡ (2)
17
 (mod 51) ⇒ 734 ≡ 217 (mod 51). (I) 
Porém, 
 ≡ 
 ≡ 
 } ⇒ 210  27 ≡ 4  26 (mod 51) ⇒ 217 ≡ 104 (mod 51) ⇒ 217 ≡ 2 (mod 51). 
Dessa forma, 2
17
 ≡ 2 (mod 51) ⇒ 217 ≡ 49 (mod 51). (II) 
De (I) e (II), temos que 7
34
 ≡ 49 (mod 51), o que indica que o resto da divisão de 7
34
 por 51 é 49. 
 
ii) Notemos que 5
3
 ≡ 9 (mod 29), o que nos dá: 5
63
 ≡ 9
21
 (mod 29). Como 9 = 3
2
, 5
63
 ≡ 3
42
 (mod 29) (I) 
Mas, 3
3
 ≡ 2 (mod 29) ⇒ 342 ≡ (2)16 (mod 29) ⇒ 342 ≡ 216 (mod 29) (II) 
No entanto, 2
8
 ≡ 13 (mod 29) ⇒ (28)2 ≡ 132 (mod 29) ⇒ 216 ≡ 169 (mod 29) ⇒ 216 ≡ 24 (mod 29) (III). 
De (I), (II) e (III), temos que 5
63
 ≡ 24 (mod 29), ou seja, o resto da divisão de 5
63
 por 29 é 24. 
 
3. Mostrar que se p é um ímpar e a2 + 2b2 = 2p, então “a” é par e “b” é ímpar. 
Teremos 4 casos: 
1º Caso: “a” par e “b” par 
Dessa forma, teremos: a = 2x e b = 2y (x e y inteiros). 
Então, a
2
 + 2b
2
 = 4x
2
 + 8y
2
 = 4(x
2
 + 2y
2
). 
Já que a
2
 + 2b
2
 = 2p, temos que 4(x
2
 + 2y
2
) = 2p ⇒ p = 2(x2 + 2y2), o que é um absurdo, pois p é ímpar. 
2º Caso: “a” ímpar e “b” par 
Dessa forma, teremos: a = 2x + 1 e b = 2y (x e y inteiros). 
Então, a
2
 + 2b
2
 = (2x + 1)
2
 + 2(2y)
2
 = 4(x
2
 + 4x + y
2
) + 1, o que é absurdo, pois a
2
 + 2b
2
 = 2p. 
3º Caso: “a” ímpar e “b” ímpar 
Dessa forma, teremos a = 2x + 1 e b = 2y + 1 (x e y inteiros) 
Então, a
2
 + 2b
2
 = (2x + 1)
2
 + 2(2y + 1)
2
 = 2(2x
2
 + 2x + 4y
2
 + 4y + 1) + 1, o que é absurdo, analogamente ao caso 2. 
4º Caso: “a” par e “b” ímpar 
Dessa forma, teremos a = 2x e b = 2y + 1 (x e y inteiros). 
Então, a
2
 + 2b
2
 = (2x)
2
 + 2(2y + 1)
2
 = 2(2x
2
 + 4y
2
 + 4y + 1). 
Dessa forma, teríamos que p = 2x
2
 + 4y
2
 + 4y + 1, verificando o fato de p ser ímpar. 
 
D s cas s , , 3 e , tere s que, para “p” í par, a
2
 + 2b
2
 = 2p somente para “a” par e “b” í par. 
 ∎ 
4. Provar que para p primo (p  1)! ≡ p  1 (mod 1 + 2 + ... + (p  1)). 
Notemos que: 
(p  1) ≡  1 (mod p) e (p  1)! ≡ 1 (mod p) (Teorema de Wilson). 
Pela transitividade, teremos que: (p  1)! ≡ p  1 (mod p). 
Isso nos mostra que p | (p  1)!  (p  1). 
Temos, também, que (p  1)!  (p  1) = (p  1)  [(p  2)!  1], ou seja, p  1 | (p  1)!  (p  1). 
Disso, segue que 
 p  
 
 | (p  1)!  (p  1). 
Como p e 
 p  
 
 são primos entre si, temos que p  
 p  
 
 | (p  1)!  (p  1), ou seja, (p  1)! ≡ p  1 ( p 
 p  
 
). 
Notando, porém, que 1 + 2 + ... + (p  1) = p  
 p  
 
, tem-se provado o resultado. 
∎ 
 
5. Encontrar o máximo divisor comum de (p  1)!  1 e p! (primo). 
Se p = 2, teremos que (p  1)!  1 = 0 e p! = 2, ou seja, mdc((p  1)!  1, p!) = mdc(0, 2) = 2. 
Se p = 3, teremos que (p  1)!  1 = 1, ou seja, mdc((p 1)!  1) = 1. Suponhamos, então, p  2. 
Seja d um divisor comum de (p  1)!  1 e de p!. 
Notemos que, se d = p, então d  (p  1)!  1. Consideremos, portanto, d  p. 
Como d | p! = p  (p  1)! e d  p, então d | (p  1)!. 
Mas d | (p  1)!  1, por hipótese. Se d | (p  1)! e d | (p  1)!  1, então d | 1, logo d = 1. 
Então, mdc((p  1)!  1, p!) = 1, se |p|  2 e mdc((p  1)!  1, p!) = 2, se |p| = 2. 
 
Nota: Do Teorema de Wilson, p | (p  1)! + 1. Dessa forma, se p | (p  1)!  1 = (p  1)! + 1  2, então p divide a 2, ou seja, 
p = 2. 
 
6. Mostrar que para n  4 o resto da divisão por 12 de 1! + 2! + ... + n! é 9. 
Queremos provar que, para n  4, o resto da divisão de 1! + 2! + ... + n! por 12 é 9. Ou seja, se N = 1! + 2! + ... + n!, 
queremos mostrar que N ≡ 9 (mod 12). 
Notemos que 1! + 2! + 3! = 9, e que 4! = 24. 
Então, 1! + 2! + 3! + 4! + ... + n! = 9 + (4! + 5! + ... + n!) = 9 + 4!(1 + 5 + 6  5 + ... + n  (n  1)  ...  6  5). 
Então, para n  4, teremos que 1! + 2! + 3! + ... + n! = 9 + 4! . k. Porém, 4! = 24 = 12  2. Então, 12 | 4!  k (k inteiro). 
Sendo assim, podemos escrever: 1! + 2! + 3! + ... + n! = 9 + 12  m (m ∈ ℤ), para n  4. 
Logo, se N = 1! + 2! + 3! + ... + n! = 9 + 12  m, então N ≡ 9 (mod 12), tendo provado o resultado. 
∎ 
 
7. Mostrar que para n inteiro 3n2  1 nunca é um quadrado. 
Notemos que 3n
2
  1 = 3n
2
  3 + 2 = 3(n  1)(n + 1) + 2 = 3k + 2. 
Basta mostrarmos que nenhum quadrado é da forma 3k + 2. 
Um número t, qualquer, pode ser das formas: t = 3k, t = 3k + 1 ou t = 3k + 2. Então, 
(I) t = 3k ⇒ t2 = 9k2 = 3  (3k2) = 3k1 
(II) t = 3k + 1⇒ t2 = (3k + 1)2 = 9k2 + 6k + 1 = 3k2 + 1 
(III) t = 3k + 2 ⇒ t2 = (3k + 2)2 = 9k2 + 12k + 4 = 3k2 + 1. 
Dessa forma, temos provado que um quadrado nunca é da forma 3k + 2 e, consequentemente, que 3n
2
  1 nunca é um 
quadrado. 
8. Resolver as seguintes congruências. 
(a) 5x ≡ 3 (mod 24) 
Vejamos que, existe y inteiro tal que: 5x = 3 + 24y, ou seja, 5x  24y = 3. 
Procuramos, portanto, soluções para essa Equação Diofantina. 
Vejamos que: 5  5  24 = 1 ⇒ (3  5)  5  3  24 = 3 ⇒ x = 15 e y = 3 é uma solução particular. 
Dessa forma, 5  (x  15)  24  (y  3) = 0 ⇒ x = 15 + 
   3 
 
 ⇒ y = 3 + 5  k ⇒ x = 15 + 24  k ⇒ x ≡ 15 (mod 24) 
Vejamos, porém, que, dada a equação ax + by = c, com d = mdc(a, b), se d | c, então para uma solução particular x = x0, 
teremos que: x = x0 + (
 b 
 
)  k (k ∈ ℤ). 
Para a nossa equação 5x  24y = 3, teremos que d = mdc(5, 24) = 1. Para x0 = 15, teremos: x = 15 + (
  
 
)  k = 15  24  k. 
Isso nos dá a solução x ≡ 15 (mod 24). 
 
(b) 3x ≡ 1 (mod 10) 
Queremos encontrar a solução da equação 3x  10y = 1. Notemos que mdc(3, 10) = 1 | 1. 
Vejamos que x = 3 e y = 1 é uma solução particular. Dessa forma, 
3  (x + 3)  10  (y + 1) = 1 ⇒ x = 3 + 
  
3
 ⇒ x = 3 + 10  k (k inteiro) ⇒ x ≡ 3 (mod 10) ⇒ x ≡ 7 (mod 10). 
 
(c) 23x ≡ 7 (mod 19) 
Queremos encontrar a solução da equação 23x  19y = 7. Vejamos que mdc(23, 19) = 1 | 7. Isso garante a existência da 
solução. 
Notemos que, 23 = 19 + 4, que 19 = 3  4 + 7, então, multiplicando a primeira igualdade por 3, teremos: 
3  23 = 3  19 + 3  4 = 3  19 + (19  7) ⇒ 3  23 + 4  19 = 7, dessa forma x = 3 e y = 4 é uma solução particular. 
Teremos, então, que 23(x + 3)  19(y + 4) = 0, o que nos dá: x =  3 + 
  
 3
 ⇒ x = 3 + 19  k (k inteiro). 
O que nos dá, como solução, a classe de congruências: x ≡ 3 (mod 19), ou seja, x ≡ 16 (mod 19). 
 
(d) 7x ≡ 5 (mod 18) 
Vejamos que mdc(7, 18) = 1 | 5, então existe solução. Dessa forma, queremos a solução da equação 7x  18y = 5. 
Temos que: 18  2  7 = 4, ou seja, 3  18  6  7 = 3  4 = 12 = (7 + 5). Então, 3  18  7  7 = 5. Assim, uma solução particular 
para a equação é x = 7 e y = 3. 
Então, 7  (x + 7)  18  (y + 3) = 0, ou seja, x = 7 + 18  k (k inteiro). 
As soluções são tais que x