lista-teoria-dos-numeros

Prévia do material em texto

Teoria dos Números
Para solução dos itens (a) e (b) da Questão 1, iremos utilizar as seguintes propriedades:
Propriedade 1. Sejam k e m inteiros, com m > 1 e (k,m) = 1. Se {a1, . . . , am} é um sis-
tema completo de reśıduos módulo m, então, para qualquer a ∈ Z, o conjunto {a+ka1, . . . , a+
kam} também é um sistema completo de reśıduos módulo m.
Prova: Para mostrar que {a + ka1, . . . , a + kam} é um sistema completo de reśıduos módulo
m, é suficiente mostrar que a + ka1, . . . , a + kam são dois-a-dois incongruentes módulo m
(pois já sabemos que tal conjunto possui m elementos). Para isso, vamos supor que existem
i, j ∈ {1, . . . ,m} tais que a+kai ≡ a+kaj(mod m). Dessa forma, vale que kai ≡ kaj(mod m)
e, como (k,m) = 1, temos ai ≡ aj(mod m) (ou seja, podemos dividir ambos os lados da
congruência por k). Dáı, como {a1, . . . , am} é um sistema completo de reśıduos, isso só
ocorre se i = j. Assim, a + ka1, . . . , a + kam são dois-a-dois incongruentes módulo m e, dáı,
{a + ka1, . . . , a + kam} é um sistema completo de reśıduos módulo m.
Propriedade 2. Seja a um inteiro positivo tal que (a,m) = 1. Se {r1, . . . , rϕ(m)} é um sis-
tema reduzido de reśıduos módulo m, então {ar1, . . . , arϕ(m)} também é um sistema reduzido
de reśıduos módulo m.
Prova: Para mostrar que {ar1, . . . , arϕ(m)} é um sistema reduzido de reśıduos módulo m,
devemos mostrar que os elementos desse conjunto são dois-a-dois incongruentes módulo m
e são coprimos com m. Primeiro, vamos mostrar que dados quaisquer i, j ∈ {1, . . . , ϕ(m)},
com i 6= j, temos que ari e arj são incongruentes módulo m. De fato, se existirem i, j tais que
ari ≡ arj(mod m), então teŕıamos ri ≡ rj(mod m), uma vez que (a,m) = 1. Por outro lado,
isso não pode ocorrer, pois {r1, . . . , rϕ(m)} é um sistema reduzido de reśıduos módulo m e,
portanto, seus elementos são dois a dois incongruentes. Agora, como (a,m) = 1 e (ri,m) = 1
para todo 1 ≤ i ≤ ϕ(m) (pois {ar1, . . . , arϕ(m)} é um sistema reduzido de reśıduos módulo
m e, portanto, seus elementos são coprimos com m), temos que (ari,m) = 1. Dessa forma,
conclúımos que os elementos de {ar1, . . . , arϕ(m)} são dois-a-dois incongruentes módulo m e
são todos coprimos com m, de modo que tal conjunto é um sistema reduzido de reśıduos
módulo m.
1
Questão 1.
(a) Considere o sistema completo de reśıduos módulo 7 canônico {0, 1, 2, 3, 4, 5, 6}. Para
cada elemento desse conjunto que é um número composto, vamos adicionar um múltiplo
de 7 até obter um número primo. Por exemplo:
0 ≡ 0 + 7 ≡ 7(mod 7)
1 ≡ 1 + 4 · 7 ≡ 29(mod 7)
3 ≡ 3(mod 7)
4 ≡ 4 + 7 ≡ 11(mod 7)
5 ≡ 5(mod 7)
6 ≡ 6 + 7 ≡ 13(mod 7)
Dessa forma, veja que {3, 5, 7, 11, 13, 29} é um sistema completo de reśıduos módulo 7.
Além disso, tal sistema é formado apenas por números primos.
(b) Inicialmente, vamos considerar o sistema reduzido de reśıduos módulo 24 canônico
{1, 5, 7, 11, 13, 17, 19, 23}. Pela Propriedade 2 temos que para qualquer inteiro a ∈ Z,
com (a, 24) = 1, o conjunto {a, 5a, 7a, 11a, 13a, 17a, 19a, 23a} é um sistema reduzido de
reśıduos módulo 24. Assim, podemos tomar, por exemplo, a = 5, e assim, observe que
(5, 24) = 1 e, portanto, {5, 25, 35, 55, 65, 85, 95, 115} é um sistema reduzido de reśıduos
módulo 24 formado apenas por múltiplos de 5.
(c) Verdadeiro apenas para n = 2.
Veja que para n = 2, temos que {0, 1} é um sistema completo de reśıduos módulo 2.
Agora, considere o caso em que n > 2 e temos o conjunto {02, 12, . . . , (n− 1)2}. Nesse
caso, temos que (n− 1)2 6= 1 e:
(n− 1)2 ≡ n2 − 2n + 1 ≡ 1(mod m)
Ou seja, existem dois elementos (1 e (n−1)2) distintos em {02, 12, . . . , (n−1)2} que são
congruentes. Dessa forma, tal conjunto não pode ser um sistema completo de reśıduos
módulo m.
2
Questão 2.
Seja n ∈ N um natural qualquer. Para mostrar que 133 divide 11n+2 + 122n+1 utilizando
congruências, basta mostrar que
11n+2 + 122n+1 ≡ 0 (mod 133).
Dessa forma, observe primeiro que:
11n+2 ≡ 11n · 112 (mod 133)
m
11n+2 ≡ 11n · 121 (mod 133)
m
11n+2 ≡ 11n · (−12) (mod 133)
e, além disso,
122n+1 ≡ (122)n · 121 (mod 133)
m
122n+1 ≡ 144n · 12 (mod 133)
m
122n+1 ≡ 11n · 12 (mod 133).
Ou seja, temos que {
11n+2 ≡ −12 · 11n (mod 133)
122n+1 ≡ 12 · 11n (mod 133)
Somando as duas congruências temos
11n+2 + 122n+1 ≡ 0 (mod 133).
Como queŕıamos.
3
Para a solução da Questão 3 e 4, usaremos o Pequeno Teorema de Fermat:
Teorema 1 (Fermat). Seja p primo. Se p - a, então ap−1 ≡ 1 (mod p).
Questão 3.
Inicialmente, observe que como m ≡ n (mod (p − 1)), temos, pela definição de con-
gruência, que existe algum k ∈ Z tal que m = k · (p− 1) + n. Dessa forma, elevando ambos
os lados da congruência x ≡ y (mod p) por m, temos
x ≡ y (mod p)
m
xm ≡ yk·(p−1)+n (mod p)
m
xm ≡ yk·(p−1) · yn (mod p).
Por outro lado, como (y, p) = 1, por hipótese, temos pelo Pequeno Teorema de Fermat
que yp−1 ≡ 1 (mod p), de modo que yk(p−1) ≡ 1k (mod p). Dessa forma, temos que
xm ≡ 1kyn (mod p).
Ou seja,
xm ≡ yn (mod p).
Como queŕıamos.
4
Questão 4.
Vamos encontrar o resto da divisão de 912 + 9! · 12 por 11 utilizando congruências.
Primeiro, temos que 912 = 910 · 92 e, além disso, veja que 92 = 81 = 7 · 11 + 4.
Dessa forma, temos que 92 ≡ 4 (mod 11) e, como 11 - 9, temos pelo Pequeno Teorema de
Fermat que 910 ≡ 1 (mod 11). Ou seja:{
910 ≡ 1 (mod 11)
92 ≡ 4 (mod 11)
Multiplicando ambas as congruências, temos que 912 ≡ 4 (mod 11).
Agora, vamos calcular o resto da divisão de 9! por 11. Para isso, veja que
9 ≡ −2 (mod 11)
8 ≡ −3 (mod 11)
7 ≡ −4 (mod 11)
6 ≡ −5 (mod 11)
5 ≡ 5 (mod 11)
4 ≡ 4 (mod 11)
3 ≡ 3 (mod 11)
2 ≡ 2 (mod 11)
1 ≡ 1 (mod 11)
Dessa forma, multiplicando as congruências acima, temos que
9! ≡ (−1)4 · 52 · 42 · 32 · 22 (mod 11).
Dáı, como
52 ≡ 25 ≡ 3 (mod 11)
42 ≡ 16 ≡ 5 (mod 11)
32 ≡ 9 ≡ −2 (mod 11)
22 ≡ 4 (mod 11)
Multiplicando as congruências acima, temos que
9! ≡ 3 · 5 · (−2) · 4 ≡ −120 ≡ 1 (mod 11).
Ou seja, 9! ≡ 1 (mod 11).
Agora, como 12 ≡ 1 (mod 11), temos que 9! · 12 ≡ 1 (mod 11).
Em resumo, provamos que
{
912 ≡ 4 (mod 11)
9! · 12 ≡ 1 (mod 11)
Somando as congruências acima, temos que 912 + 9! · 12 ≡ 5 (mod 11). Ou seja, o resto
da divisão de 912 + 9! · 12 por 11 é igual a 5.
5
Para a solução da Questão 5, usaremos o Teorema de Euler:
Teorema 2 (Euler). Se m, a ∈ Z são inteiros tais que (m, a) = 1 e m > 1, então
aϕ(m) ≡ 1 (mod m).
Questão 5.
(a) Iremos encontrar o resto da divisão de 1022+1121+1220 por 50 utilizando congruências.
Para isso, iremos primeiro encontrar, separadamente, o resto da divisão de 1022, 1121 e
1220 por 50 utilizando congruências.
(i) Resto da divisão de 1022 por 50
Primeiro, observe que
102 ≡ 100 ≡ 0 (mod 50).
Dáı, como 1022 = (102)11, temos que
1022 ≡ 011 ≡ 0 (mod 50).
Ou seja, 1022 ≡ 0 (mod 50).
(ii) Resto da divisão de 1121 por 50
Primeiro, observe que
ϕ(50) = ϕ(2 · 25) = ϕ(2 · 52) = 52 − 5 = 20.
Dáı, pelo Teorema de Euler, como (11, 50) = 1 temos que 1120 ≡ 1 (mod 50).
Dessa forma, temos que
1121 ≡ 1120 · 11 ≡ 1 · 11 ≡ 11 (mod 50).
Ou seja, 1121 ≡ 11 (mod 50).
(iii) Resto da divisão de 1220 por 50
Nesse caso, como 1220 = 320 · 420, vamos primeiro encontrar, separadamente, o
resto da divisão de 320 e 420 por 50 e, em seguida, multiplicar os restos.
Inicialmente, observe que (3, 50) = 1, de modo que, pelo Teorema de Euler, temos
que 320 ≡ 1 (mod 50).
6
Agora, veja que
44 ≡ 256 ≡ 6 (mod 50).
Além disso, temos que
64 ≡ 1296 ≡ 46 ≡ −4 (mod 50).
Assim, temos que 65 ≡ 64 · 6 ≡ −4 · 6 ≡ −24 ≡ 26 (mod 50). Dessa forma, temos
420 ≡ (44)5 ≡ 65 ≡ 26 (mod 50).
Dáı, temos que {
320 ≡ 1 (mod 50)
420 ≡ 26 (mod 50)
Multiplicando as duas congruências, temos que 1220 ≡ 26 (mod 50).
Dessa forma, pelos itens (i), (ii) e (iii), conclúımos que
1022 ≡ 0 (mod 50)
1121 ≡ 11 (mod 50)
1220 ≡ 26 (mod 50)
Somando as congruências, obtemos
1022 + 1121 + 1220 ≡ 37 (mod 50).
Ou seja, o resto da divisão de 1022 + 1121 + 1220 por50 é igual a 37.
(b) Vamos encontrar o resto da divisão de 14 + . . .+ 1004 por 6 usando congruências. Para
isso, observe que os posśıveis restos na divisão de qualquer número positivo por 6 é um
elemento de {0, 1, . . . , 5}. Agora, veja que
04 ≡ 64 ≡ 0 (mod 6)
14 ≡ 1 (mod 6)
24 ≡ 16 ≡ 4 (mod 6)
34 ≡ 81 ≡ 3 (mod 6)
44 ≡ 256 ≡ 4 (mod 6)
54 ≡ 625 ≡ 1 (mod 6)
Agora, como 100 = 16 · 6 + 4, temos que
14 + 24 . . . + 1004 ≡ 16 · (14 + 24 + 34 + 44 + 54 + 64) + (14 + 24 + 34 + 44) (mod 6).
7
Dessa forma, temos que
14 + 24 . . . + 1004 ≡ 16 · (1 + 4 + 3 + 4 + 1 + 0) + (1 + 4 + 3 + 4) (mod 6).
Ou seja,
14 + 24 . . . + 1004 ≡ 16 · 13 + 12 (mod 6)
m
14 + 24 . . . + 1004 ≡ 16 · 13 (mod 6).
m
14 + 24 . . . + 1004 ≡ 16 (mod 6).
m
14 + 24 . . . + 1004 ≡ 4 (mod 6).
Logo, o resto da divisão de 14 + 24 . . . + 1004 por 6 é igual a 4.
8
Para a solução do item (a) da Questão 6, vamos utilizar o Critério de Euler:
Teorema 3 (Critério de Euler). Se p for um primo ı́mpar e a um inteiro não-diviśıvel por
p, então (
a
p
)
≡ a(p−1)/2 (mod p).
Questão 6.
(a) Inicialmente, veja que 167 = 2 · 83 + 1 é um primo ı́mpar. Dessa forma, temos que
M83 ≡ 283 − 1 (mod 167).
m
M83 ≡ 2(167−1)/2 − 1 (mod 167).
m
M83 ≡
(
2
167
)
− 1 (mod 167).
A última congruência acima decorre do Critério de Euler, uma vez que (2, 167) = 1.
Por outro lado, como 167 ≡ 8 · 20 + 7 ≡ 7 (mod 8) e, além disso,(
2
167
)
= (−1)k,
com k =
[
2
167
]
+
[
2 · 2
167
]
+ . . . +
[
167−1
2
2
167
]
, então teremos que
(
2
167
)
= 1.
Dessa forma, temos que
M83 ≡
(
2
167
)
− 1 (mod 167)
m
M83 ≡ 0 (mod 167).
Ou seja, temos que 167 divide M83. Como desejado.
(b) Inicialmente, observe que podemos escrever 641 de duas formas:
641 = 27 · 5 + 1
641 = 24 + 54
9
Pela primeira forma, temos que
27 · 5 ≡ −1 (mod 641).
Dáı, elevando ambos os lados da congruência acima à quarta potência, temos
228 · 54 ≡ 1 (mod 641).
Por outro lado, pela segunda forma, temos que
54 ≡ −24 (mod 641).
Assim, das duas congruências acima, temos que
228 · 54 ≡ 1 (mod 641)
m
228 · (−2)4 ≡ 1 (mod 641)
m
−232 ≡ 1 (mod 641).
Ou seja, temos que 641 divide 232 + 1 = 22
5
+ 1. Como queŕıamos.
10