Question

(Aritmética: Congruência modular – classe inversa)

Sejam $n,\,k$ números naturais, $n\ge 1.$ Mostre que

a) Se $k$ é ímpar, então

$3n+1$ é divisível por $2^k,$ mas não é divisível por $2^{k+1}$ se e somente se $n\equiv \dfrac{(2^{k+2}+1)(2^k-1)}{3}~\pmod{2^{k+1}}.$

b) Se $k$ é par, então

$3n+1$ é divisível por $2^k,$ mas não é divisível por $2^{k+1}$ se e somente se $n\equiv \dfrac{(2^{k+1}+1)(2^k-1)}{3}~\pmod{2^{k+1}}.$

──────

Obs.: Caso necessário, utilize as congruências a seguir:

     $3\cdot \left(\dfrac{2^{k+2}+1}{3}\right)\equiv 1~\pmod{2^{k+1}},$ se $k$ é ímpar.

     $3\cdot \left(\dfrac{2^{k+1}+1}{3}\right)\equiv 1~\pmod{2^{k+1}},$ se $k$ é par.

Answer 1

a)

Antes de simplificar a congruência, desejo demonstrar que a simplificação da fração à qual n é congruente é de mão dupla, ou seja, se pode tanto ir quanto voltar a ela. Para isso, a fração deve ser um inteiro, ou seja, o numerador deve ser congruente a 0, mod 3. Testemos com k ímpar, já que é o único caso que interessa ao enunciado:

$(2^{k+2} + 1)(2^k - 1) \equiv 0 \pmod 3\\\Rightarrow(2^{(2q + 1)+2} + 1)(2^{2q + 1} - 1) \equiv 0 \pmod 3\\\Rightarrow(2^{2q} \cdot 2^3 + 1)(2^{2q} \cdot 2 - 1) \equiv 0 \pmod 3\\\Rightarrow(4^q \cdot 8 + 1)(4^q \cdot 2 - 1) \equiv 0 \pmod 3\\\Rightarrow(1^q \cdot 2 + 1)(1^q \cdot 2 - 1) \equiv 0 \pmod 3\\\Rightarrow(1 \cdot 2 + 1)(1 \cdot 2 - 1) \equiv 0 \pmod 3\\\Rightarrow3 \cdot 1 \equiv 0 \pmod 3\\\Rightarrow0 \equiv 0 \pmod 3$

Ou seja, se pode tanto ir quanto voltar à fração inicial, com k ímpar.

Simplificando a congruência dada no enunciado:

$n \equiv \cfrac{(2^{k+2} + 1)(2^k - 1)}{3} \pmod {2^{k + 1}}\\\\\Leftrightarrow 3n \equiv 2^{k+2} \cdot (2^k - 1) + 1 \cdot (2^k - 1) \pmod {2^{k + 1}}\\\Leftrightarrow 3n \equiv 2^{k+1} \cdot 2 \cdot (2^k - 1) + (2^k - 1) \pmod {2^{k + 1}}\\\Leftrightarrow 3n \equiv 2^k - 1 \pmod {2^{k + 1}}\\\Leftrightarrow 3n + 1 \equiv 2^k \pmod {2^{k + 1}}\:\:\:(i)$

$\Leftrightarrow 6n + 2 \equiv 2^{k+1}\pmod {2^{k+1}}\\\Leftrightarrow 3n + 1 \equiv 2^{k}\pmod {2^{k}}\\\Leftrightarrow 3n + 1 \equiv 0\pmod {2^{k}}\:\:\:(ii)$

$(i)\:2^{k + 1} \nmid 3n + 1\\(ii)\:2^k \mid 3n + 1$

A ida é válida. Agora basta demonstrar o retorno. Percebendo que $2^{k+1} = 2^k \cdot 2$, podemos representar essa divisibilidade por $2^k$ mas não por $2^{k+1}$ escrevendo $3n+1$ como um produto de $2^k$ com um outro termo que não tenha 2 em sua decomposição em primos, ou seja, um ímpar:

$3n+1 = 2^k \cdot (2q + 1)\\\Rightarrow 3n + 1 = q \cdot 2^{k+1} + 2^k\\\Rightarrow 3n + 1 \equiv 2^k \pmod {2^{k+1}}$

Congruência da qual se pode retornar à inicial, conforme demonstrado anteriormente.

$2 \nmid k \implies (2^k \mid 3n + 1 \land 2^{k+1} \nmid 3n + 1) \Leftrightarrow n \equiv \cfrac{(2^{k+2}+1)(2^k - 1)}{3} \pmod {2^{k+1}}$

b)

Testando paridade na fração congruente a n (somente com k par, conforme solicitado no enunciado):
$(2^{k+1}+1)(2^k - 1) \equiv 0 \pmod 3\\\Rightarrow (2^{2q} \cdot 2)(2^{2q} - 1) \equiv 0 \pmod 3\\\Rightarrow (4^q \cdot 2)(4^q - 1) \equiv 0 \pmod 3\\\Rightarrow (1^q \cdot 2)(1^q - 1) \equiv 0 \pmod 3\\\Rightarrow (1 \cdot 2)(1 - 1) \equiv 0 \pmod 3\\\Rightarrow 2 \cdot 0 \equiv 0 \pmod 3\\\Rightarrow 0 \equiv 0 \pmod 3$

Se pode tanto ir quanto voltar, com k par.

Simplificando a congruência:

$n \equiv \cfrac{(2^{k+1} + 1)(2^k - 1)}{3} \pmod {2^{k + 1}}\\\\\Leftrightarrow 3n \equiv 2^{k+1} \cdot (2^k - 1) + 1 \cdot (2^k - 1) \pmod {2^{k + 1}}\\\Leftrightarrow 3n \equiv 2^k - 1 \pmod {2^{k + 1}}\\\Leftrightarrow 3n + 1 \equiv 2^k \pmod {2^{k + 1}}$

Do que, de modo idêntico à alínea a, se pode concluir a não-divisibilidade por $2^{k+1}$ e a divisibilidade por $2^k$. E de modo também idêntico, se pode escrever $3n+1$ como $2^k \cdot (2q + 1)$, e retornar à congruência inicial, conforme demonstrado com os conectivos lógicos ⇔ acima.

$2 \mid k \implies (2^k \mid 3n + 1 \land 2^{k+1} \nmid 3n + 1) \Leftrightarrow n \equiv \cfrac{(2^{k+1}+1)(2^k - 1)}{3} \pmod {2^{k+1}}$