2014 1 AD2 A1 Gabarito(1)

Prévia do material em texto

A´lgebra I
AD2 - Segunda Avaliac¸a˜o a Distaˆncia - Aulas 10 a 14
1a Questa˜o: [2, 0 pontos] Dado um nu´mero positivo qualquer n, seja n1 o resultado de sub-
trair o dobro do algarismo das unidades ao nu´mero que se obte´m eliminando esse algarismo
em n; por exemplo, se n = 2472 enta˜o n1 = 247 − 2 × 2 = 243. Verifca-se que n e divis´ıvel
por 7 se e so´ se n1 tambe´m o for. Repetindo esse procedimento descrito, pode-se testar a
divisibilidade por 7 sem efetuar a divisa˜o. Vejamos um exemplo! Pelo que foi descrito, testar
se 2472 e´ divis´ıvel por 7 e´ equivalente a verificar se 243 e´ divis´ıvel por 7, que por sua vez
e´ equivalente a verificar se 18 e´ divis´ıvel por 7. Como 18 na˜o e´ divis´ıvel por 7 enta˜o 2472
tambe´m na˜o e´.
Justifique porque esse crite´rio de divisibilidade funciona.
Soluc¸a˜o: Seja n um inteiro positivo qualquer. Sabemos que podemos respresentar n =
arar−1...a1a0 da seguinte forma, veja a Aula 10 pa´gina 37 do mo´dulo,
n = ar10
r + ar−110r−1 + ...+ a110 + a0.
Agora, pondo 10 em evideˆncia na expressa˜o acima, podemos reescrever n como
n = 10
(
ar10
r−1 + ...+ a1
)
+ a0 = 10b+ a,
onde a = a0 e b = ar10
r−1 + ...+ a1.
Perceba que ao eliminarmos o algarismo das unidades em n obtemos o nu´mero
arar−1...a1 = ar10r−1 + ...+ a1 = b.
Dessa forma, segundo o enunciado do exerc´ıcio, deveremos provar que
7 | a+ 10b⇐⇒ 7 | b− 2a.
Utilizando as propriedades de congrueˆncias segue-se que
7 | a+ 10b⇐⇒ 10b ≡ −amod 7⇐⇒ 3b ≡ −amod 7
⇐⇒ b ≡ −5amod 7⇐⇒ b ≡ 2amod 7⇐⇒ 7 | b− 2a.
1
2a Questa˜o: [2, 0 pontos] Determinar quais os valores poss´ıveis de
φ (2n)
φ (n)
onde φ denota a
func¸a˜o φ de Euler.
Sugesta˜o: Analise separadamente os casos n par e n ı´mpar.
Soluc¸a˜o: Vamos analisar separadamene os casos em que n e´ par e n e´ ı´mpar.
Se n e´ ı´mpar enta˜o
φ (2n) = φ (2)φ (n) = φ (n) , logo
φ (2n)
φ (n)
= 1.
Se n e´ par enta˜o podemos representa´-lo como n = 2km, com k ≥ 1 e m ı´mpar. Dessa
forma teremos
φ (n) = φ
(
2km
)
= φ
(
2k
)
φ (m) = 2k−1 (2− 1)φ (m) = 2k−1φ (m) .
Do mesmo modo teremos
φ (2n) = φ
(
2k+1m
)
= φ
(
2k+1
)
φ (m) = 2k+1−1 (2− 1)φ (m) = 2kφ (m) .
Portanto,
φ (2n)
φ (n)
=
2kφ (m)
2k−1φ (m)
= 2.
Conclusa˜o,
φ (2n)
φ (n)
=
 1, se n e´ ı´mpar2, se n e´ par.
3a Questa˜o: [2, 0 pontos] Determine:
(a) 0 ≤ a < 73 satisfazendo 9794 ≡ amod 73.
(b) 0 ≤ a < 83 satisfazendo 7670 ≡ amod 83.
Soluc¸a˜o:
(a) Como 73 e´ primo, pelo Teorema de Fermat, sabemos que
972 ≡ 1 mod 73. (1)
Por outro lado, como 794 = 11× 72 + 2, enta˜o
9794 = 911×72+2 =
(
972
)11
92.
2
De (1) concluimos que (
972
)11 ≡ 1 mod 73
e dessa forma (
972
)11
92 ≡ 92 ≡ 8 mod 73.
Conclusa˜o:
9794 ≡ 8 mod 73, isto e´, a = 8.
(b) Sendo 83 primo, usaremos a mesma ideia do item (a). Pelo Teorema de Fermat sabemos
que
782 ≡ 1 mod 83.
Como 670 = 8 × 82 + 14, teremos que determinar a congrueˆncia de 714 mod 83. Para isso
podemos observar que 14 = 8 + 4 + 2 e
72 = 49 ≡ −34 mod 83
73 ≡ 11 mod 83 =⇒ 74 ≡ 77 ≡ −6 mod 83,
e dessa forma 78 = (74)
2 ≡ (−6)2 = 36 mod 83.
Logo,
714 = 78 × 74 × 72 ≡ (36)× (−6)× (−34) ≡ 40 mod 83.
Finalmente,
7670 =
(
782
)8
714 ≡ (1)× (40) mod 83.
Conclusa˜o: a = 40.
4a Questa˜o: [2, 0 pontos] Um nu´mero escrito com cem algarismos iguais a 0, cem algarismos
iguais a 1 e cem algarismos iguais a 2 pode ser um quadrado perfeito? (Dica: Use crite´rios
de divisibilidade simples)
Soluc¸a˜o: Seja N o nu´mero em questa˜o. Observe que se um primo p aparece na decomposic¸a˜o
de um nu´mero natural n, enta˜o o nu´mero p2 divide n2. Logo se um primo p divide um
quadrado perfeito n, enta˜o p2 tambe´m divide n.
3
Como a soma dos algarismos de N e´ 100(0 + 1 + 2) = 300, conclu´ımos que 3 divide N .
Pelo observado acima, se N e´ um quadrado perfeito, enta˜o 9 tambe´m divide N . Lembre-
se que um nu´mero natural e´ divis´ıvel por 9 se, e somente se, a soma de seus algarismos e´
divis´ıvel por 9. Contudo 9 na˜o divide 300, portanto, N na˜o e´ um quadrado perfeito.
5a Questa˜o: [2, 0 pontos] Seja aoa1 · · · an−1an = an + an−110 + · · · + a110n−1 + ao10n a
representac¸a˜o decimal de um nu´mero natural, isto e´, aj ∈ {0, 1, 2, · · · , 9}.
(a) Prove que aoa1 · · · an−1an ≡ an−1an mod 4 e conclua um crite´rio de divisibilidade por 4.
(b) O u´ltimo algarismo (algarismo das unidades) do quadrado de um nu´mero natural n e´ 6.
Prove que o penu´ltimo algarismo de n2 e´ ı´mpar.
Soluc¸a˜o:
(a) Conforme o enunciado temos aoa1 · · · an−1an = an+an−110+· · ·+a110n−1+ao10n. E´ fa´cil
ver que 10k ≡ 0 mod 4 para todo k ≥ 2 ja´ que neste caso 10k = 4× 25× 10k−2. Portanto,
an + an−110 + · · ·+ a110n−1 + ao10n ≡ an + an−110 mod 4.
Ou seja, aoa1 · · · an−1an ≡ an−1an mod 4.
Sabemos que um nu´mero N e´ divis´ıvel por 4 se, e somente se, N ≡ 0 mod 4. Logo um
nu´mero e´ divis´ıvel por 4 se, e semente se, quando expresso na base 10, seus dois u´ltimos
algarismos da direita (na ordem em que aparecem) formam um nu´mero divis´ıvel por 4.
(b) Seja N o nu´mero em questa˜o. Observe que N e´ par, pois termina em 6. Se N = M2,
o natural M = 2k para algum k ∈ N (verifique que se n2 e´ par, enta˜o n e´ par). Assim
N = M2 = 4k2, logo N e´ divis´ıvel por 4. Portanto, se escrevemos N = aoa1 · · · an−1an, a
representac¸a˜o decimal de N , conclu´ımos que an−1an e´ divis´ıvel por 4 pelo crite´rio estabelecido
no item (a). O nu´mero an−1an e´ 06, 16, 26, 36, 46, 56, 66, 76, 86 ou 96. Uma inspec¸a˜o direta
garante que apenas 16, 36, 56, 76 e 96 sa˜o divis´ıveis por 4. Logo an−1 e´ ı´mpar.
4