Question

(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.​

Answer 1

Partindo desde 3n + 1:

$3n + 1$ pode ser escrito como $8q + 4$, com $q \in \mathbb{Z}$, para representar a divisibilidade por 4 mas não por 8. Logo:

$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$

━━━━━━━

Partindo desde n ≡ 1 (mod 8):

$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$

E também:
$3n + 1 = 4 \cdot 2k + 4\\3n + 1 = 4(2k + 1)$

Então 3n + 1 não é múltiplo de 8 e é múltiplo de 4, sempre que n ≡ 1 (mod 8).

$\boxed {n \equiv 1 \pmod 8 \Leftrightarrow 4 \mid 3n + 1 \land 8\nmid 3n + 1 }$