AP2 A1 2016 1 Gabarito

Prévia do material em texto

A´lgebra 1
Soluc¸o˜es da AP2
Questa˜o 1: (2,0 pontos) Seja N = anan−1 · · · a1ao a representac¸a˜o de um nu´mero natural
na base 10. Mostre que N e´ divis´ıvel por 11 se, e somente se, a soma
ao − a1 + · · ·+ (−1)
n−1an−1 + (−1)
nan
e´ divis´ıvel por 11.
Soluc¸a˜o: Primeiramente lembramos que um nu´mero natural N e´ divis´ıvel por 11 se, e
somente se, N ≡ 0( mod 11). A expressa˜o N = anan−1 · · · a1ao equivale a
N = 10nan + 10
n−1an−1 + · · ·+ 10
1a1 + ao.
Enta˜o, N ≡ 0( mod 11) se, e somente se, 10nan + 10
n−1an−1 + · · · + 10
1a1 + ao ≡ 0(
mod 11). Como 101 ≡ −1( mod 11), temos 10k ≡ (−1)k( mod 11) para todo k ∈. Usando
as propriedades de congrueˆncias obtemos
N ≡ ao − a1 + · · ·+ (−1)
n−1an−1 + (−1)
nan( mod 11).
Portanto, N e´ divis´ıvel por 11 se, e somente se, o nu´mero ao−a1+· · ·+(−1)
n−1an−1+(−1)
nan
e´ divis´ıvel por 11.
Questa˜o 2: (1,0 ponto) Determine o inverso multiplicativo de 29 em Z121.
Soluc¸a˜o:
Note que mdc (29, 121) = 1. De fato,
4 5 1 4
121 29 5 4 1
5 4 1 0
Basta agora encontrar inteiros r e s tais que
29r + 121s = 1,
1
pois assim teremos
29 · r + 0 = 1⇐⇒ r e´ o inverso de 29 em Z121.
Tem-se enta˜o
• 121 = 29 · 4 + 5
• 29 = 5 · 5 + 4
• 5 = 4 · 1 + 1
Da´ı vem que,
1 = 5− 4 · 1 = 5− (29− 5 · 5) = 1 · 5 + 5 · 5− 29 · 1 = 6 · 5− 29 · 1 =
= 6 · (121− 4 · 29)− 29 = 6 · 121− 24 · 29− 29 = 6 · 121− 25 · 29.
Sendo r = −25 enta˜o como −25 ∈ 96 ( pois, 121 − 25 = 96 ) segue que 96 e´ o inverso
multiplicativo de 29 em Z121.
Questa˜o 3: (1,0 ponto) Resolva a equac¸a˜o 29x− 2 = 3, em Z121
Soluc¸a˜o: Veja que
29x− 2 = 3 =⇒ 29x = 3 + 2 = 5 =⇒ x = 96 · 29x = 96 · 5 = 480 = 117
Conclusa˜o: x = 117.
Questa˜o 4: (2,0 pontos) Utilize o Teorema de Fermat para obter o resto da divisa˜o de
25432675 por 13.
Soluc¸a˜o: A segunda versa˜o do Teorema de Fermat nos diz que
qp−1 ≡ 1 (mod p) ,
onde p e´ primo e q e´ um inteiro tal que p na˜o divide q.
Dividindo 5432675 por 12 obtemos
5432675 = 452722× 12 + 11.
2
Aplicando o Teorema de Fermat concluimos que
213−1 ≡ 1 (mod 13) ,
donde
212×452722 ≡ 1 (mod 13)
e portanto
25432675 ≡ 211 (mod 13) .
Agora, como 211 ≡ 7 (mod 13) concluimos que o resto procurado e´ 7.
Questa˜o 5: (2,0 pontos) Para pintar um pre´dio sa˜o necessa´rios 250 litros de tinta que sa˜o
vendidas em latas de 3 e de 18 litros. De quantas maneiras podemos comprar as tintas de
modo que a sobra seja mı´nima?
Soluc¸a˜o: Seja x o nu´mero de latas de tinta de 3 litros e y o nu´mero de latas de 18 litros que
precisamos comprar para obter 250 litros de tinta. Temos que 3x+18y = 250. Contudo esta
equac¸a˜o diofantina na˜o possui soluc¸a˜o pois 3 = mdc(3, 18) na˜o divide 250. Enta˜o precisamos
comprar 252 litros de tinta porque 3 tambe´m na˜o divide 251. Passemos agora a resolver a
equac¸a˜o
3x+ 18y = 252.
Dividindo os dois lados por 3 obtemos a equac¸a˜o x + 6y = 84. Como o coeficiente de x e´ 1
podemos chamar y de t e obter a soluc¸a˜o


x = 84− 6t
y = t , t ∈ Z.
E´ claro que precisamos de t ≥ 0 e x = 84−6t ≥ 0, logo t ≤ 14. Portanto, t ∈ {0, 1, 2, · · · , 14}.
Resposta: Podemos comprar as tintas de 15 modos diferentes.
Questa˜o 6: (2,0 pontos) Um grupo de 17 crianc¸as, ao tentar dividir igualmente entre si os
doces conseguidos no dia de Cosme e Damia˜o pelo grupo, verificou que haveria uma sobra
de 3 doces. Seguiu-se uma discussa˜o, na qual uma crianc¸a foi embora. Na nova tentativa de
divisa˜o, ja´ com uma crianc¸a a menos, verificou-se que haveria uma sobra de 10 doces. Nova
3
confusa˜o, e outra crianc¸a foi embora. Enfim eles conseguiram dividir igualmente os doces
entre si. Qual e´ o menor nu´mero de doces que as crianc¸as podem ter arrecadado?
Soluc¸a˜o: Denotemos por x o nu´mero de doces arrecadados pelas crianc¸as. Enta˜o o
problema descrito na questa˜o e´ equivalente ao seguinte sistema de congrueˆncias:


x ≡ 3 (mod 17)
x ≡ 10 (mod 16)
x ≡ 0 (mod 15) .
Seguindo o algoritmo apresentado no EP sobre o Teorema Chineˆs dos Restos tem-se:
n = 17× 16× 15 = 4080
N1 =
4080
17
= 240, mdc (240, 17) = 1 = 113× 17− 8× 240 donde r1 = −8
N2 =
4080
16
= 255, mdc (255, 16) = 1 = 16× 16− 1× 255 donde r2 = −1
N3 =
4080
15
= 272, mdc (272, 15) = 1 = 127× 15− 7× 2272 donde r3 = −7.
Portanto, x0 = 3× (−8)× 240 + 10× (−1)× 255 + 0× (−7)× 272 = −8310 e toda soluc¸a˜o
do sistema e´ da forma
x = −8310 + 4080t, t ∈ Z.
Como estamos interessados no primeiro valor positivo de x, fazendo t = 3 obtemos x = 3930
que e´ o menor nu´mero de doces que as crianc¸as podem ter conseguido.
4