Solução EP08

Prévia do material em texto

Álgebra I - Soluções dos EP8
1a Questão: Determine o resto da divisão de 560 por 26.
Solução: Escrevendo 560 = 26q + r, observe que o nosso problema equivale a determinar o
inteiro r, 0 ≤ r ≤ 25 tal que
560 ≡ r (mod 26) .
Note então que de 52 = 25 conclúımos que
52 ≡ −1 (mod 26) .
Dáı vem que (52)
2 ≡ (−1)2 (mod 26), ou seja, 54 ≡ 1 (mod 26).
Como 560 = (54)
15
então (
54
)15 ≡ 115 (mod 26) ,
donde conclúımos que 1 é o resto da divisão de 560 por 26.
2a Questão: Calcule o resto da divisão de N = 3345678 por 7, 11 e 13.
Solução:
• Resto da divisão de N = 3345678 por 7.
Note que 33 ≡ −1 (mod 7). Dividindo 345678 por 3 obtém-se
345678 = 3× 115226 + 0.
Portanto,
3345678 = 33×115226 =
(
33
)115226
.
De 33 ≡ −1 (mod 7) vem que (33)115226 ≡ (−1)115226 (mod 7) =⇒ (33)115226 ≡ (−1) (mod 7).
Donde o resto da divisão de N por 7 é 1.
• Resto da divisão de N por 11.
1
Observe que
35 = 243 ≡ 1 (mod 11) . (1)
Dividindo 345678 por 5 obtém-se
345678 = 5× 69135 + 3.
Portanto,
3345678 =
(
35
)69135 × 33.
De (1) vem que (
35
)69135 ≡ 1 (mod 11)
e dáı concluimos que (
35
)69135 × 33 ≡ 27 (mod 11) .
Tem-se então que N − 27 = 11k, para algum k inteiro. Sendo 27 = 2× 11 + 5 então
N = 11 (k + 2) + 5.
Ou seja, o resto da divisão de N por 11 é 5.
• Resto da divisão de N por 13.
Note inicialmente que
33 ≡ 1 (mod 13) . (2)
Dividindo 345678 por 3 vem que 345678 = 3× 115226 + 0. Portanto,
3345678 = 33×115226 =
(
33
)115226
.
De (2) segue que (
33
)115226 ≡ 1 (mod 13) ,
donde conclúımos que N − 1 = 13k para algum k inteiro. Portanto 1 é o resto da divisão de
N por 13.
3a Questão: Utilize congruências para verificar que 23 | 211 − 1.
Solução:
2
É suficiente observar que
211 =
(
25
)2 · 2,
e que, sendo
25 ≡ 9 (mod 23)
então (25)
2 ≡ 92 (mod 23) e portanto
(
25
)2 · 2 ≡ 92 · 2 (mod 23) ,
isto é,
211 ≡ 162 (mod 23) .
Por outro lado como
162 ≡ 1 (mod 23) ,
conclúımos que
211 ≡ 1 (mod 23) ,
ou seja, 23 | 211 − 1.
4a Questão: Determine o resto das divisões:
(a) De 250 por 7;
(b) De 4165 por 7.
Solução:
(a) Observe inicialmente que
250 = 248 · 4 =
(
23
)16 · 4.
Por outro lado,
23 = 8 ≡ 1 (mod 7) =⇒ (23)16 ≡ 116 (mod 7) =⇒ 248 ≡ 1 (mod 7)
4 ≡ 4 (mod 7)
 =⇒ 250 ≡ 1·4 (mod 7)
=⇒ 250 = 7k + 4, o que mostra que o resto procurado é 4.
(b) Basta notar que
41 ≡ −1 (mod 7)
3
e dáı vem que
4165 ≡ (−1)65 (mod 7) ,
isto é,
4165 ≡ (−1) (mod 7) .
Portanto, 4165 + 1 = 7k, para algum k ∈ Z. Dáı segue que 4165 = 7 (k − 1) + 6, donde
conclúımos que o resto procurado é igual a 6.
5a Questão: Mostre, utilizando indução sobre m, que
(10)2m ≡ 1 (mod 11) , ∀ m ∈ Z+.
Solução: (i) Para m = 0 tem-se que
1− 1 = 0 = 11× 0 =⇒ 1 ≡ 1 (mod 11) .
(ii) Assumimos como verdade que
(10)2k ≡ 1 (mod 11) ,
isto é,
(10)2k − 1 = 11s, para algum s ∈ Z. (HI)
(iii) Vamos provar que (10)2(k+1) ≡ 1 (mod 11).
De fato,
(10)2k+2 = (10)2k (10)2 e (10)2 = 1 + 9× 11.
Como por (HI), (10)2k = 11s + 1, então
(10)2k+2 = (1 + 9× 11) (1 + 11s) = 1 + (s + 9 + 9s× 11)× 11.
Donde segue que,
(10)2k+2 − 1 = 11S,
com S = s + 9 + 9s× 11. Ou seja,
(10)2k+2 ≡ 1 (mod 11) .
4
Imagine que lecionando para uma turma de Ensino Médio você fale de critérios de divis-
ibilidade. Um estudante observa enquanto você lista aquelas regras e pergunta: “Mas, isso
é verdade mesmo? Como você fez para encontrar essas regras?”. Você dá alguns exemplos,
usa as regras, depois divide para verificar que a regra está funcionando. Então o estudante
implacável pergunta: “E isso vale pra qualquer número (inteiro) que você colocar áı?!”. Para
evitar que você responda algo como “Pra explicar eu precisaria usar congruências, que é uma
coisa que a gente vê só na Universidade.” criamos o exerćıcio a seguir que tem por objetivo
encontrar os critérios de divisibilidade sem utilizar congruência. Observe que a justificativa
é essencialmente a mesma.
Seja N um número natural. Escrevendo N na base 10 temos
N = ao + 10a1 + 10
2a2 + · · ·+ 10nan.
Uma maneira heterodoxa de se obter o critério de divisibilidade por 2 é obtida escrevendo-
se
N = ao + 10(a1 + 10a2 + · · ·+ 10n−1an)
e observar que N é diviśıvel por 2 se, e somente se, ao é diviśıvel por dois.
Para se obter o critério de divisibilidade por 3 podemos escrever
N = (ao + a1 + · · ·+ an) + [(10− 1)a1 + (100− 1)a2 + · · ·+ (10n − 1)an]
e então observar que o número entre colchetes é diviśıvel por três. Logo N é diviśıvel por
três se, e somente se, ao + a1 + · · ·+ an é diviśıvel por três.
A questão a seguir foi inspirada no artigo Sobre Critérios de Divisibilidade publicado na
Revista do Professor de Matemática com autoria de C. M. G. Táboas e H. de S. Ribeiro.
6a Questão: Utilizando como modelo os critérios de divisibilidade por 2 e por 3 dados acima
determine os critérios de divisibilidade por 5, 9 e 11 sem utilizar congruências.
Solução:
Critério de divisibilidade por 5. Escrevendo N na base 10 e colocando 10 em evidência temos
N = ao + 10(a1 + 10a2 + · · ·+ 10n−1an).
Como 5 divide 10(a1 + 10a2 + · · · + 10n−1an), temos que 5 divide N = ao + 10(a1 + 10a2 +
· · · + 10n−1an) se, e somente se, 5 divide ao. Como ao ∈ {0, 1, 2 · · · , 9}, 5 divide N se, e
5
somente se, ao = 0 ou ao = 5.
Critério de divisibilidade por 9. Escrevendo N na base 10 e manipulando um pouco obtemos
N = (ao + a1 + · · ·+ an) + [(10− 1)a1 + (100− 1)a2 + · · ·+ (10n − 1)an].
Observe que a expressão entre colchetes é 9a1 + 99a2 + · · ·+ (10n − 1)an, que é diviśıvel por
9. Logo, 9 divide N se, e somente se, 9 divide ao + a1 + · · ·+ an.
Critério de divisibilidade por 11. Assim como antes podemos manipular a expressão N =
ao + 10a1 + 10
2a2 + · · ·+ 10nan e obter
N = ao − a1 + · · ·+ (−1)nan + [11a1 + 99a2 + · · ·+ (10n − (−1)n)an]
. Assim, 11 divide N se, e somente se, 11 divide ao − a1 + · · · + (−1)nan, já que a parcela
entre colchetes é sempre diviśıvel por 11.
7a Questão: Considere o número N = 4100.
(a) Qual é o d́ıgito das unidades de N na base 10?
(Dica: Observe que 6n ≡ 6 mod 10 qualquer que seja n ∈ N− {0})
(b) N é diviśıvel por 3?
Solução: O algarismo das unidades de um número escrito na base 10 é o menor elemento
não-negativo de sua classe de congruência módulo 10. Então queremos encontrar x tal que
4100 ≡ x mod 10. Sabemos que 42 ≡ 6 mod 10 e que 62 ≡ 6 mod 10, então 4100 = (42)50 ≡
650 mod 10. Também 650 ≡ 6 mod 10. Logo 4100 ≡ 6 mod 10. Conclusão: O d́ıgito das
unidades de 4100 é 6. Para o item b) basta observar que como 4 ≡ 1 mod 3, também 4100 ≡ 1
mod 3. Logo, o resto da divisão de 4100 por 3 é 1. Portanto, N não é diviśıvel por 3.
6