AP3 A1 2013 2 Gabarito

Prévia do material em texto

A´lgebra I - AP3
Questa˜o 1: Um nu´mero da forma Fn = 2
2n + 1, n ∈ N, e´ chamado nu´mero de Fermat.
Prove, utilizando o Princ´ıpio da Induc¸a˜o Finita, que
F0 · F1 · F2 · ... · Fn−1 = Fn − 2, n ≥ 1.
Soluc¸a˜o:
Para n = 1 tem-se,
F0 = 2
20 + 1 = 3 = (22
1
+ 1)− 2 = F1 − 2,
ou seja, a fo´rmula e´ verdadeira para n = 1;
Admitindo a validade da expressa˜o para n = k, isto e´,
F0 · F1 · F2 · ... · Fk−1 = Fk − 2,
vamos provar que ela e´ verdadeira para n = k + 1. De fato,
F0 · F1 · F2 · ... · Fk−1 · Fk = (Fk − 2) · Fk =
[
(22
k
+ 1)− 2
]
·
[
22
k
+ 1
]
=
=
[
22
k − 1
]
·
[
22
k
+ 1
]
=
(
22
k
)2
− 12 = 22k·2 − 1 = 22k+1 − 1 =
=
(
22
k+1
+ 1
)
− 2 = Fk+1 − 2.
Questa˜o 2: 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) Dados a e b inteiros, aZ ⊂ bZ⇔ b | a.
(b) Dados a,b e m inteiros, se 2a ≡ 2b(modm), enta˜o a ≡ b(modm).
Soluc¸a˜o:
(a) Verdadeira
• Supondo que aZ ⊂ bZ, tem-se que a ∈ bZ e, portanto, existe k ∈ Z tal que a = kb.
Logo, b | a.
1
• Observe que, x ∈ aZ, se e somente se, existe k ∈ Z tal que x = ka. Supondo que b | a,
existe k ∈ Z tal que a = kb. Logo, x = k(kb) = (kk)b e, portanto, x ∈ bZ. Sendo x
arbitra´rio, conclui-se que aZ ⊂ bZ.
(b) Falsa
Para m = 2, a = 4 e b = 3, tem-se que 8 ≡ 6 (mod 2) , mas na˜o vale 4 ≡ 3 (mod 2) .
Questa˜o 3: Determine o resto da divisa˜o de 2101 + 8986 por 7.
Soluc¸a˜o:
Observe inicialmente que
23 ≡ 1 (mod 7) ,
e como 101 = 3 · 33 + 2 enta˜o (
23
)33 · 22 ≡ 22 (mod 7)
donde vem que
2101 = 7k1 + 4. (0.0.1)
Por outro lado, como 7 e´ primo e 7 na˜o divide 898 enta˜o, pelo pequeno Teorema de Fermat
(segunda versa˜o), segue que
8987−1 ≡ 1 (mod 7) ,
isto e´,
8986 = 7k2 + 1. (0.0.2)
Somando as expresso˜es em (0.0.1) e (0.0.2) obtemos
2101 + 8986 = 7 (k1 + k2) + 5,
o que nos mostra que o resto na divisa˜o de 2101 + 8986 por 7 e´ 5.
Questa˜o 4: Dado um nu´mero natural na base 10, digamos N = a0a1a2 · · · ak, os d´ıgitos aj,
com 0 ≤ j ≤ k, sa˜o nu´meros naturais menores que 10.
(a) Escreva o nu´mero N como soma de mu´ltiplos inteiros de poteˆncias de 10 (Por exemplo,
se 2013 = 2 · 103 + 0 · 102 + 1 · 101 + 3 · 100).
2
(b) Use a expressa˜o obtida no item anterior e os seus conhecimentos de congrueˆncias
para mostrar que o nu´mero natural N e´ mu´ltiplo de 3 se, e somente se, a soma dos seus
d´ıgitos e´ um mu´ltiplo de 3.
Soluc¸a˜o:
(a) N = ao · 10k + a1 · 10k−1 + a2 · 10k−2 + · · ·+ ak · 100.
(b) Esta e´ a Proposic¸a˜o 2 da Aula 10 no mo´dulo. Confira sua soluc¸a˜o.
Questa˜o 5: Uma empresa quer adquirir 125 litros de um determinado l´ıquido que e´ vendido
em recipientes de 7 ou 15 litros.
(a) (0,5 ponto) Determine a equac¸a˜o Diofantina linear que modela o problema.
(b) (1,5 ponto) Qual a quantidade de cada recipiente a empresa deve adquirir?
Soluc¸a˜o:
(a) Denotando por x e y o nu´mero de recipientes de 15l e 7l, respectivamente, o problema
consiste em obter uma soluc¸a˜o particular da equac¸a˜o diofantina linear
15x + 7y = 125.
(b) Como mdc(15, 7) = 1 e 1 | 125, a equac¸a˜o possui soluc¸a˜o. Utilizando o Algoritmo de
Euclides para obter inteiros r e s tais que r× 15 + s× 7 = 1, obe´m-se r = 1 e s = −2. Dessa
forma, tem-se que
1× 15 + (−2)× 7 = 1 =⇒ 125(1× 15 + (−2)× 7) = 125× 1 =⇒ 125× 15 + (−250)× 7 = 125
e, portanto, x0 = 125 e y0 = −250 formam uma soluc¸a˜o particular da equac¸a˜o. Sendo assim,
todas as soluc¸o˜es sa˜o da forma
x = x0 − 7
mdc(15, 7)
t = 125− 7
1
t = 125− 7t
y = y0 +
15
mdc(15, 7)
t = −250 + 15
1
t = −250 + 15t
com t ∈ Z.
Observe que, pela natureza do problema, devemos ter valores na˜o-negativos para x e y,
ou seja,
125− 7t ≥ 0 =⇒ t ≤ 125
7
≈ 17, 8
−250 + 15t ≥ 0 =⇒ t ≥ 250
15
≈ 16, 7.
3
Dessa forma, a u´nica soluc¸a˜o para o problema corresponde a t = 17, isto e´,
x = 125− 7× 17 = 6 e y = −250 + 15× 17 = 5.
Resposta: 6 recipientes de 15l e 5 recipientes de 7l.
4