(Aritmética: Congruência modular – classe inversa)
Seja [tex]n[/tex] um número natural ≥ 1, e [tex]q[/tex] o quociente da divisão de [tex]2^n[/tex] por 3. Mostre que
a) [tex]3(2^n-q)\equiv 1~\pmod{2^n}[/tex] se e somente se [tex]n[/tex] é par.
b) [tex]3(q+1)\equiv 1~\pmod{2^n}[/tex] se e somente se [tex]n[/tex] é ímpar.
────────
Obs.: Nas alíneas a) e b), os números [tex]2^n-q[/tex] e [tex]q+1[/tex] são os menores representantes positivos da classe inversa do 3, módulo [tex]2^n[/tex] para [tex]n[/tex] par e [tex]n[/tex] ímpar respectivamente.
Seja [tex]n[/tex] um número natural ≥ 1, e [tex]q[/tex] o quociente da divisão de [tex]2^n[/tex] por 3. Mostre que
a) [tex]3(2^n-q)\equiv 1~\pmod{2^n}[/tex] se e somente se [tex]n[/tex] é par.
b) [tex]3(q+1)\equiv 1~\pmod{2^n}[/tex] se e somente se [tex]n[/tex] é ímpar.
────────
Obs.: Nas alíneas a) e b), os números [tex]2^n-q[/tex] e [tex]q+1[/tex] são os menores representantes positivos da classe inversa do 3, módulo [tex]2^n[/tex] para [tex]n[/tex] par e [tex]n[/tex] ímpar respectivamente.
More Questions From This User See All
Lista de comentários
Verified answer
Definição que será utilizada em ambos os itens:
[tex]2^n = 3q +r\\\\q = \cfrac{2^n - r}{3}[/tex]
a)
[tex]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}[/tex]
Ou seja, o resto da divisão de [tex]2^n[/tex] por 3 é congruente a 1, módulo [tex]2^n[/tex]. O resto, por definição, é maior que 0 e menor que [tex]2^n[/tex], portanto se pode afirmar que [tex]r = 1[/tex]. Então:
[tex]2^n = 3q + 1\\\Rightarrow2^n \equiv 1 \pmod 3[/tex]
n somente pode ser par. Demonstração:
[tex]2^{2k}\\\equiv (2^2)^k\\\equiv 4^k\\\equiv 1^k\\\equiv 1 \pmod 3\:\:\:(i)[/tex]
Plausível.
[tex]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)[/tex]
Não plausível.
Resumindo, se [tex]3(2^n - q) \equiv 1 \pmod {2^n}[/tex], então n é par. Agora há de se provar a sentença partindo desde n par:
[tex]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}[/tex]
───────────
b)
[tex]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}[/tex]
A definição do resto diz que este é maior que 0 e menor que [tex]2^n[/tex], portanto [tex]r = 2[/tex]. Como visto em (i) e (ii), no item a, n deve ser ímpar. Provado isto, agora basta demonstrar o retorno:
[tex]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}[/tex]