Verified answer

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:

[tex](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[/tex]

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

Simplificando a congruência dada no enunciado:

[tex]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)\\[/tex]

[tex]\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)\\\\[/tex]

[tex](i)\:2^{k + 1} \nmid 3n + 1\\(ii)\:2^k \mid 3n + 1[/tex]

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

[tex]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}}[/tex]

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

[tex]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}}[/tex]

b)

Testando paridade na fração congruente a n (somente com k par, conforme solicitado no enunciado):
[tex](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[/tex]

Se pode tanto ir quanto voltar, com k par.

Simplificando a congruência:

[tex]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}}[/tex]

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

[tex]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}}[/tex]