Question

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

Seja $n$ um número natural ≥ 1, e $q$ o quociente da divisão de $2^n$ por 3. Mostre que

a) $3(2^n-q)\equiv 1~\pmod{2^n}$ se e somente se $n$ é par.

b) $3(q+1)\equiv 1~\pmod{2^n}$ se e somente se $n$ é ímpar.

────────

Obs.: Nas alíneas a) e b), os números $2^n-q$ e $q+1$ são os menores representantes positivos da classe inversa do 3, módulo $2^n$ para $n$ par e $n$ ímpar respectivamente.​

Answer 1

Definição que será utilizada em ambos os itens:
$2^n = 3q +r\\\\q = \cfrac{2^n - r}{3}$

a)

$3(2^n - q) \equiv 1 \pmod {2^n}\\\\\Rightarrow -3q \equiv 1 \pmod {2^n}\\\\\Rightarrow -3(\cfrac{2^n - r}{3}) \equiv 1 \pmod {2^n}\\\\\Rightarrow r \equiv 1 \pmod {2^n}$

Ou seja, o resto da divisão de $2^n$ por 3 é congruente a 1, módulo $2^n$. O resto, por definição, é maior que 0 e menor que $2^n$, portanto se pode afirmar que $r = 1$. Então:
$2^n = 3q + 1\\\Rightarrow2^n \equiv 1 \pmod 3$

n somente pode ser par. Demonstração:

$2^{2k}\\\equiv (2^2)^k\\\equiv 4^k\\\equiv 1^k\\\equiv 1 \pmod 3\:\:\:(i)$

Plausível.

$2^{2k+1}\\\equiv (2^2)^k \cdot 2\\\equiv 4^k \cdot 2\\\equiv 1^k \cdot 2 \\\equiv 1 \cdot 2\\\equiv 2 \pmod3\:\:\:(ii)$

Não plausível.

Resumindo, se $3(2^n - q) \equiv 1 \pmod {2^n}$, então n é par. Agora há de se provar a sentença partindo desde n par:

$2^{2k} \equiv 0 \pmod {2^{2k}}\\\Rightarrow 2^{2k} \equiv 0 \pmod {2^{2k}}\\\Rightarrow 2 \cdot 2^{2k} \equiv 0 \pmod {2^{2k}}\\\Rightarrow 3 \cdot 2^{2k} - 2^{2k} + 1 \equiv 1 \pmod {2^{2k}}\\\Rightarrow 3 \cdot 2^{2k} - 3(\cfrac{2^{2k} + 1}{3} ) \equiv 1 \pmod {2^{2k}}\\\\\Rightarrow 3 (2^{2k} - (\cfrac{2^{2k} + 1}{3} )) \equiv 1 \pmod {2^{2k}}\\\\\Rightarrow 3 (2^{2k} - q) \equiv 1 \pmod {2^{2k}}\\\\\boxed{3 (2^{n} - q) \equiv 1 \pmod {2^{n}} \Leftrightarrow 2 \mid n}$

───────────

b)

$3(q+1) \equiv 1 \pmod {2^n}\\\\\Rightarrow 3( \cfrac{2^n-r}{3}+1) \equiv 1 \pmod {2^n}\\\\\Rightarrow 2^n-r + 3 \equiv 1 \pmod {2^n}\\\Rightarrow r \equiv 2 \pmod {2^n}$

A definição do resto diz que este é maior que 0 e menor que $2^n$, portanto $r = 2$. Como visto em (i) e (ii), no item a, n deve ser ímpar. Provado isto, agora basta demonstrar o retorno:
$2^{2k + 1} \equiv 0 \pmod {2^{2k + 1}}\\\Rightarrow 2^{2k + 1} + 1 \equiv 1 \pmod {2^{2k + 1}}\\\Rightarrow 2^{2k + 1} - 2 + 3 \equiv 1 \pmod {2^{2k + 1}}\\\Rightarrow 3(\cfrac{2^{2k + 1} - 2}{3} + 1 ) \equiv 1 \pmod {2^{2k + 1}}\\\\\Rightarrow 3(q + 1 ) \equiv 1 \pmod {2^{2k + 1}}\\\\\boxed{3(q + 1 ) \equiv 1 \pmod {2^{n}} \Leftrightarrow 2 \nmid n}$