Question

(Aritmética: Decomposição em fatores primos e divisibilidade)

Seja n um número natural, n ≥ 1. Mostre que

a) Se n ≡ 3 (mod 4), então 3n + 1 é par, mas não é divisível por 4.

b) Se 3n + 1 é par, mas não é divisível por 4, então n ≡ 3 (mod 4).

─────

Obs: Em Matemática, a conjunção das proposições das alíneas a) e b) é indicada através do conectivo lógico ⟺.

     lê-se: "se e somente se" ou "é equivalente a".

No caso desta tarefa, provamos que

     n ≡ 3 (mod 4)   ⟺   3n + 1 é par, mas não é divisível por 4.

Proposta para leitura/estudo: Conjectura de Collatz.​

Answer 1

a)

$n \equiv 3 \pmod 4\\n = 4k + 3\\n = 2 \cdot 2k + 2 + 1\\n = 2k' + 1$

n é ímpar.

$n \equiv 3 \pmod 4\\3n \equiv 9 \pmod 4\\3n \equiv 1 \pmod 4\\3n + 1 \equiv 2 \pmod 4\\\\3(2k' + 1) + 1 \equiv 2 \pmod 4\\6k' + 3 + 1 \equiv 2 \pmod 4\\2 \cdot 3k' + 2^2 \equiv 2 \pmod 4\\2q \equiv 2 \pmod 4$

Logo, 3n + 1 é par, e não é congruente a 0, mod 4.

b)

$2(2q + 1)$ é um modo de dizer "o dobro de um ímpar". Desse modo, sempre será par, mas nunca divisível por 4 (pois, para isso, deveria ser divisível por $2 \cdot 2$, mas $2q + 1$ não é divisível por 2).

$3n + 1 \equiv 2(2q+1) \pmod 4\\3n \equiv 4q + 2 - 1 \pmod 4\\3n \equiv 1 \pmod 4$

Multiplicando 3n pela classe inversa de 3, mod 4:
$3(3n) \equiv 3 \cdot 1 \pmod 4\\9n \equiv 3 \pmod 4\\n \equiv 3 \pmod 4$