(Aritmética: Decomposição em fatores primos e divisibilidade)
Seja n um número natural, n ≥ 1. Mostre que
n ≡ 1 (mod 8) se e somente se 3n + 1 é divisível por 4, mas não é divisível por 8.
─────
Obs: Recomenda-se que a prova de uma proposição "se e somente se" seja feita em duas partes. Uma para provar a implicação direta, e a outra para provar a implicação recíproca.
Em continuação ao conteúdo abordado na tarefa https://brainly.com.br/tarefa/53259116
Proposta para leitura/estudo: Conjectura de Collatz.
[tex]3n + 1[/tex] pode ser escrito como [tex]8q + 4[/tex], com [tex]q \in \mathbb{Z}[/tex], para representar a divisibilidade por 4 mas não por 8. Logo:
gabrielcguimaraes
Duas dúvidas: 1 - Está correta a notação destacada no final? 2 - É necessário o caso "partindo de 3n + 1" ou o segundo caso (partindo desde a congruência dada) é suficiente para determinar a sentença?
Lukyo
1. A notação está perfeita. Logicamente formidável. 2: Sim, é necessário partir de um lado para chegar ao outro e também partir do outro para chegar ao primeiro. Assim que se demonstra uma equivalência lógica (se e somente se).
Lukyo
Nem sempre a recíproca é verdadeira, por isso deve-se verificar os dois sentidos.
Lista de comentários
Verified answer
Partindo desde 3n + 1:
[tex]3n + 1[/tex] pode ser escrito como [tex]8q + 4[/tex], com [tex]q \in \mathbb{Z}[/tex], para representar a divisibilidade por 4 mas não por 8. Logo:
[tex]3n + 1 \equiv 8q + 4 \pmod 8\\3n + 1 \equiv 4 \pmod 8\\3n \equiv 3 \pmod 8\\3 \cdot 3n \equiv 3 \cdot 3 \pmod 8\\9n \equiv 9 \pmod 8\\n \equiv 1 \pmod 8[/tex]
━━━━━━━
Partindo desde n ≡ 1 (mod 8):
[tex]n \equiv 1 \pmod 8\\n = 8q + 1\\3n = 24q + 3\\3n + 1 = 24q + 4\\3n + 1 = 8 \cdot 3q + 4\\3n + 1 = 8k + 4[/tex]
E também:
[tex]3n + 1 = 4 \cdot 2k + 4\\3n + 1 = 4(2k + 1)[/tex]
Então 3n + 1 não é múltiplo de 8 e é múltiplo de 4, sempre que n ≡ 1 (mod 8).
[tex]\boxed {n \equiv 1 \pmod 8 \Leftrightarrow 4 \mid 3n + 1 \land 8\nmid 3n + 1 }[/tex]
1 - Está correta a notação destacada no final?
2 - É necessário o caso "partindo de 3n + 1" ou o segundo caso (partindo desde a congruência dada) é suficiente para determinar a sentença?