AP3 A1 2014 2 Gabarito

Prévia do material em texto

A´lgebra I
Soluc¸o˜es da AP3
Questa˜o 1: (1,5 pontos) Mostre usando induc¸a˜o matema´tica que 2 | (3n − 1) para todo
n ∈ N.
Soluc¸a˜o: Para n = 1 temos que 2 | 2. Suponhamos que a afirmac¸a˜o seja verdadeira para n,
ou seja, existe um inteiro k tal que 3n − 1 = 2k. Mostremos que a afirmac¸a˜o e´ va´lida para
n + 1.
De fato, 3n+1 − 1 = 3n × 3− 1 = (2k + 1)× 3− 1 = 6k + 3− 1 = 6k + 2 = 2× (3k + 1),
isto e´, 2 | (3n+1 − 1).
Questa˜o 2: (1,5 pontos) Os restos das diviso˜es dos inteiros 4933 e 4435 por um inteiro
positivo n sa˜o respectivamente 37 e 19. Obtenha os poss´ıveis valores de n.
Soluc¸a˜o: Como os restos na divisa˜o por n sa˜o 37 e 19 respectivamente, enta˜o n divide
4896 = 4933− 37 e 4416 = 4435− 19. Dessa forma n e´ um divisor comum de 4896 e 4416 e
portanto n divide mdc (4896, 4416).
Calculando esse mdc obtemos 96. Temos enta˜o que n | 96 e n e´ maior que 37, donde
concluimos que n = 48 ou n = 96.
Questa˜o 3: (3,0 pontos) Determine se cada uma das afirmac¸o˜es abaixo e´ verdadeira ou
falsa. Prove as que julgar verdadeiras e apresente um contra-exemplo para as falsas:
(a) (1,0 ponto) Se a, b e c sa˜o numeros inteiros positivos quaisquer cujos restos na divisa˜o
por 8 sa˜o 3, 5 e 1 enta˜o o resto da divisa˜o de (a + b + c) por 8 e´ 1.
(b) (1,0 ponto) O conjunto I = {m ∈ Z; 46m e´ divis´ıvel por 7} e´ um ideal de Z.
(c) (1,0 ponto) O resto na divisa˜o de 11104 + 1 por 17 e´ 0.
Soluc¸a˜o:
(a) Verdadeira.
1
De fato, tem-se que
a ≡ 3 (mod 8)
b ≡ 5 (mod 8)
c ≡ 1 (mod 8) ,
e dessa forma a+ b+ c ≡ 9 (mod 8). Sendo 9 ≡ 1 (mod 8) conclui-se enta˜o que (a + b + c) ≡
1 (mod 8).
(b) Verdadeira.
Observe, inicialmente que x ∈ I ⇐⇒ existe um inteiro q tal que 46x = 7q.
• 0 ∈ I, pois 46 · 0 = 0 = 0 · 7.
• Se x, y ∈ I, enta˜o existem inteiros q1 e q2 tais que 46x = 7q1 e 46y = 7q2.. Assim
46(x− y) = 7(q1 − q2)
e, portanto, (x− y) ∈ I.
• Se x ∈ I, enta˜o existe um inteiro q tal que 46x = 7q. Assim, para todo r ∈ Z,
46rx = 7rq e, portanto, rx ∈ I.
(c) Verdadeira.
Pelo pequeno Teorema de Fermat tem-se que
1116 ≡ 1 (mod 17) . (1)
Como 104 = 16× 6 + 8 enta˜o de (1) obtemos que
(
1116
)6
118 ≡ 118 (mod 17) . (2)
Por outro lado, notemos que
112 ≡ 2 (mod 17)
e da´ı vem que (
112
)4 ≡ 24 (mod 17) ,
2
isto e´, 118 ≡ 16 (mod 17). Como 16 ≡ (−1) (mod 17) obtemos enta˜o que
118 ≡ (−1) (mod 17) . (3)
De (2) e (3) concluimos que
11104 =
(
1116
)6
118 ≡ (−1) (mod 17)
e portanto, 17 divide 11104 + 1.
Questa˜o 4: (2,0 pontos) Determine as duas menores frac¸o˜es positivas que tenham 13 e 17
como denominadores e cuja soma seja igual a
305
221
.
Soluc¸a˜o: Sejam
x
13
e
y
17
as frac¸o˜es procuradas. Notemos que desejamos que
x
13
+
y
17
=
305
221
,
isto e´,
17x + 13y
13× 17 =
305
221
. Como 13×17 = 221 nosso problema se reduz a obter x e y positivos
tais que 17x+ 13y = 305. Como mdc (17, 13) = 1 enta˜o a equac¸a˜o diofantina possui soluc¸a˜o.
De 17 = 13×1+4 e 13 = 4×3+1 obtemos que 1 = 13−4×3 = 13− (17− 13× 1)×3 =
17× (−3) + 13× (4). Portanto,
305 = 17× (−3× 305) + 13× (4× 305) = 17× (−915) + 13× (1220) .
Logo as soluc¸o˜es sa˜o x = −915 + 13t e y = 1220 − 17t com t ∈ Z. Como procuramos
x > 0 e y > 0, fazendo −915 + 13t > 0 e 1220− 17t > 0 iremos encontrar 70, 38 < t < 71, 76
donde concluimos que t = 71. Assim sendo x = 8 e y = 13 sa˜o os valores procurados.
Questa˜o 5: (2,0 pontos) Uma certa revendedora Chinesa de automo´veis possuia 1200
ve´ıculos em seu pa´tio antes de realizar uma promoc¸a˜o de 24 horas. Apo´s a promoc¸a˜o foi
observado que se os ve´ıculos fossem estacionados em fileiras 5 em 5 sobrariam 3 carros. Em
fileiras de 6 em 6, tambe´m sobrariam 3 carros. Quando postos em fileiras de 7 em 7, sobraria
1 carro. E finalmente quando postos em fileiras de 11 em 11, na˜o sobraria nenhum ve´ıculo.
Quantos carros foram vendidos apo´s as 24 horas de promoc¸a˜o?
Soluc¸a˜o:
Observa-se que o problema pode ser descrito por meio do seguinte sistema de congrueˆncias
x ≡ 3(mod 5)
x ≡ 3(mod 6)
x ≡ 1(mod 7)
x ≡ 0(mod 11).
3
Como 5, 6, 7 e 11 sa˜o relativamente primos dois a dois enta˜o podemos aplicar o Teorema do
Resto Chineˆs. Aqui vamos seguir os passos descritos no EP referente a este assunto.
Seja enta˜o n = 5 · 6 · 7 · 11 e consideremos
N1 = 6 · 7 · 11 = 462, N2 = 5 · 7 · 11 = 385, N3 = 5 · 6 · 11 = 330 e N4 = 5 · 6 · 7 = 210.
Agora
Como mdc (5, 462) = 1 enta˜o 1 = 185× 5− 2× 462
Como mdc (6, 385) = 1 enta˜o 1 = 1× 385− 6× 64
Como mdc (7, 330) = 1 enta˜o 1 = 1× 330− 7× 47
Como mdc (11, 210) = 1 enta˜o 1 = 1× 210− 19× 11
Portanto,
x0 = 3× (−2)× 462 + 3× 1× 385 + 1× 1× 330 + 0 = −1287
e´ uma soluc¸a˜o do nosso sistema e toda outra soluc¸a˜o e´ da forma
x = −1287 + 2310t com t ∈ Z.
Como devemos ter 0 < x < 1200, enta˜o t = 1 nos fornece que o nu´mero de ve´ıculos restantes
foi 1023. Logo foram vendidos 177 carros.
4