UFOP - Universidade Federal de Ouro Preto
ICEB - Departamento de Matemática
3a Prova de Fundamentos de Álgebra MTM 249 - Turma 11
Matrı́cula:
Aluno:
Nota:
1) Três satélites passarão sobre o Recife-PE à noite. O primeiro a 1 hora da madrugada, o segundo
às 4 horas e o terceiro ás 8 horas da manhã. Cada satélite tem um perı́odo diferente. O primeiro
leva 13 horas para completar uma volta em torno da Terra; o segundo, 15 horas e, o terceiro, 19
horas. Determine quantas horas decorrerão, a partir da meia-noite, até que os três satélites passem
ao mesmo tempo sobre à cidade do Recife.
2) Enuncie o Teorema de Wilson e calcule o resto da divisão de 18! por 19.
3) Verifique as seguintes afirmações:
a) 561|(3561 − 3);
7
9
b) Os algarismos das unidades de 77 e 99 são 3 e 9 respectivamente.
c) O resto da divisão de a13 por 7 é igual a a para todo inteiro a.
4) Enuncie o pequeno Teorema Fermat e use o mesmo para provar que:
a) Se p é um número primo, então ap ≡ a( mod p) para todo inteiro a;
b) Seja a ∈ Z. Se p e q são primos distintos tais que ap = a( mod q) e aq = a( mod p), então
apq = a( mod pq).
c) Mostre que, se o mdc(a, 35) = 1, então o resto da divisão de a12 por 35 é 1.
5) Algumas das afirmações abaixo são falsas (F) e outras são verdadeiras (V). Argumente convenientemente para verificar quais são (V) e quais são (F).
a) Nem todo inteiro tem inverso módulo m;
b) a ∈ Z tem inverso módulo m se, e somente se, mdc(a, m) = 1;
c) Se mdc(a, m) = 1, então a tem um ”único”inverso módulo m;
d) O inverso de 2 módulo 5 é 62.
BOA SORTE
Gabarito
1) Seja T o números de horas decorridos a partir
ao mesmo tempo sobre à cidade, então temos

 T ≡ 1
T ≡ 4
 T ≡ 8
da meia-noite, até que os três satélites passem
mod 13
mod 15
mod 19
(1)
Segue do Teorema Chinês do resto que (1) tem única solução módulo 13.15.19. Como o sistema de
congru encia é simples, vamos resolvê-lo por substituição, passo a passo. Resolvendo a primeira
equação de (1) temos que
T = 13m + 1 onde m ∈ Z,
(2)
daı́ substituindo o valor de T na segunda (1) e resolvendo vem
13m + 1
⇒ 13m
⇒ −2m
⇒ −14m
⇒ m
≡
≡
≡
≡
≡
4
3
3
21
6
mod
mod
mod
mod
mod
15
15
15
15
15,
⇒
⇒
⇒
⇒
ou seja, m = 15l + 6, onde l ∈ Z. Substituindo em (2) temos
T = 195l + 79 onde l ∈ Z.
(3)
Substituindo o valor de T na terceira equação de (1) e resolvendo segue que
195l + 79
⇒ 5l + 3
⇒ 5l
⇒ l
≡
≡
≡
≡
8 mod 19 ⇒
8 mod 19 ⇒
5 mod 19 ⇒
1 mod 19,
ou seja, l = 19t + 1 onde l ∈ Z. Novamente substituindo em (3) obtemos que
T = 3705t + 274, onde t ∈ Z.
Portanto são necessárias 274 horas a partir da meia-noite, até que os três satélites passem ao
mesmo tempo sobre à cidade.
2) Teorema Wilson Se p é um número primo, então (p − 1)! ≡ −1 mod p.
Como 19 é um número primo, segue do Teorema de Wilson que
18! = (19 − 1)! ≡ −1
≡ 18
mod 19
mod 19.
Portanto o resto da divisão de 18! por 19 é 18.
3)
a) Dizer que 561|(3561 − 3) é equivalente a dizer que 3561 ≡ 3 mod 561. Note que 561 = 3.11.17
e além disso temos que:
3561 = 3.3560 ≡
0 mod 3
561
10 56
56
3 = (3 ) .3 ≡ 1 .3 mod 11 Pequeno Teorema de Fermat
3561 = (316 )35 .3 ≡ 135 .3 mod 17 Pequeno Teorema de Fermat.
(4a)
(4b)
(4c)
Tomando X = 3561 e resolvendo (4a) temos
X = 3m onde m ∈ Z.
Substituindo (5) em (4b) temos que
3m ≡ 3
m ≡ 1
mod 11
mod 11
2
pois mdc(3, 11) = 1
(5)
ou seja, m = 11t + 1, onde t ∈ Z. Substituindo em (5) temos
X = 33t + 3 onde t ∈ Z.
(6)
Daı́ substituindo (6) em (4c) temos
33t + 3
11t
154t
t
≡
≡
≡
≡
3 mod 17
pois mdc(33, 17) = 1
0 mod 17
14.0 mod 17
0 mod 17.
Logo t = 17s, s ∈ Z e substituindo em (6) temos que X = 561s + 3, com s ∈ Z, ou seja
3561 ≡ 3 mod 561 como querı́amos.
7
9
b) Basta provarmos que 77 ≡ 3 mod 10 e 99 ≡ 9 mod 10.
7
Primeiro mostremos que 77 ≡ 3 mod 10. Note que 10 = 2.5 e do Pequeno Teorema de
7
Fermat 77 ≡ 1 mod 2, 77 = (74 ).73 ≡ 73 mod 5, 73 = 343 ≡ 3 mod 5 e 39 = (34 )2 .3 ≡ 3
mod 5, daı́
7
≡ 1
mod 2
(7a)
77
≡ 3
mod 5,
(7b)
77
7
7
daı́ fazendo X = 77 em (7a) e resolvendo temos que
X = 2m + 1 onde m ∈ Z.
(8)
Substituindo em (7b) vem
2m + 1 ≡ 3 mod 5
2m ≡ 2 mod 5
m ≡ 1 mod 5.
mdc(2, 5) = 1
Logo m = 5l + 1, onde l ∈ Z. Substituindo em (8) segue que X = 10l + 3, onde l ∈ Z.
7
Portanto segue 77 ≡ 3 mod 10.
9
Agora provaremos que 99 ≡ 9 mod 10. Note que 10 = 2.5 e do Pequeno Teorema de Fermat
9
99 ≡ 1 mod 2, 99 = (94 )2 .9 ≡ 4 mod 5 e 49 = (44 )2 .4 ≡ 4 mod 5, daı́
9
≡ 1
mod 2
(9a)
99
≡ 4
mod 5
(9b)
99
9
9
daı́ fazendo X = 99 em (9a) e resolvendo temos que
X = 2m + 1 onde m ∈ Z.
(10)
Substituindo em (9b) vem
2m + 1
2m
6m
m
≡ 4 mod 5
≡ 3 mod 5
≡ 9 mod 5
≡ 4 mod 5.
Logo m = 5l + 4, onde l ∈ Z. Substituindo em (10) segue que X = 10l + 9, onde l ∈ Z.
9
Portanto segue 99 ≡ 9 mod 10.
3
c) Basta mostrar que a13 ≡ a mod 7. Se 7 - a, segue do Pequeno Teorema de Fermat que a6 ≡ 1
mod 7 e como a7 ≡ a mod 7 para todo a ∈ Z segue que
a13 ≡ a mod 7.
Se 7|a, então a ≡ 0 mod 7, daı́ a13 ≡ 0 mod 7, logo
a13 ≡ a mod 7.
4)Pequeno Teorema de Fermat Se p é um número primo e p - a, então ap−1 ≡ 1 mod p.
a) Seja a ∈ Z. Se p|a temos a ≡ 0 mod p e, assim, ap ≡ 0 mod p. Logo, pelas propriedades
simétrica e transitiva, obtemos ap ≡ a mod p.
Se p - a, então, pelo Teorema de Fermat, ap−1 ≡ 1 mod p. Portanto, a.ap−1 ≡ a.1 mod p,
isto é, ap ≡ a mod p.
b) Pelo ı́tem a) temos (aq )p ≡ aq mod p e (ap )q ≡ ap mod q. Por hipótese temos aq ≡ a mod p
e ap ≡ a mod q. Logo, obtemos:
apq ≡ a mod p e apq ≡ a mod q ⇒ p|(apq − a) e q|(apq − a) ⇒ pq|(apq − a)
pois mdc(p, q) = 1. Portanto,
apq ≡ a mod pq.
c) Basta provarmos que a12 ≡ 1 mod 35. Note que 35 = 7.5 e como mdc(a, 35) = 1, temos que
7 - a e 5 - a. Assim usando Pequeno Teorema de Fermat temos que
a6 ≡ 1
mod 7 e a4 ≡ 1
mod 5,
logo
a12 ≡ 1 mod 5
a12 ≡ 1 mod 7,
(11a)
(11b)
ou seja, a12 = 5m + 1, onde m ∈ Z, substituindo em (11b), temos
5m + 1 ≡ 1 mod 7
5m ≡ 0 mod 7
m ≡ 0 mod 7.
Assim m = 7l, onde l ∈ Z e a12 = 5(7l) + 1, ou seja a12 ≡ 1 mod 35.
3)
a) De fato, tome 2 ∈ Z4 = {0, 1, 2, 3}, note que
2.0 = 0, 2.1 = 2, 2.2 = 0 e 2.3 = 2,
isto é, 2 é um inteiro que não tem inverso módulo 4 .
b) Suponha que a ∈ Z tenha inverso módulo m, então ax ≡ 1 mod m, ou seja ax − my = 1
para algum inteiro y, logo mdc(a, m) = 1.
Suponha que mdc(a, m) = 1, então existem r e s inteiros tais que ar + ms = 1, disto segue
que ar ≡ 1 mod m.
4
c) Suponha que a tenha dois inversos módulo m, a saber, b e b0 , então
a.b ≡ 1 mod m
a.b0 ≡ 1 mod m,
então a.b ≡ a.b0 mod m e como mdc(a, m) = 1, segue que b ≡ b0 mod m, ou seja, o inverso
é único.
d) Falso, pois
2.62 ≡ 4
5
mod 5.