[Aritmética: Teoria dos Números – Números naturais – Congruência modular – Equações não-lineares]
Resolva a equação de congruência modular, com n ∈ ℕ:
2ⁿ ≡ 2n + 1 (mod 3).
─────
Obs.: Resolver a equação é equivalente a descrever quais são todas as soluções para o problema, e mostrar que não existem outras soluções além das que você indicar.
Gentileza demonstrar com detalhes e de forma clara, justificando cada passagem do seu desenvolvimento, caso contrário, a sua resposta não será considerada correta. Obrigado.
Vamos usar (i) e (ii) para encontrar a solução da nossa equação de congruência de maneira mais simples. Se fizermos uso de (i), temos que fazer n = 2k + 1, portanto, substituindo isso em nossa equação de congruência modular, temos:
Da congruência anterior temos que o mdc(4, 3) = 1 e por definição 2 é divisível por 1, portanto existe solução. Se existe solução para a congruência anterior, existe um inteiro y, tal que:
O que acabamos de ter é uma equação diofantina, essa equação diofantina pode ser resolvida pelo algoritmo de Euclides, mas observe que não é complexa de resolver. Observe que se t = 1 podemos ver que:
Lista de comentários
Verified answer
Resposta:
Após os devidos cálculos feitos, podemos concluir que n ∈ {6q + r: r ∈ {0, 5} e q ∈ ℕ}.
Explicação passo-a-passo:
O problema nos pede para resolver a seguinte equação de congruência modular, com n ∈ ℕ:
⟹ 2ⁿ ≡ 2n + 1 (mod 3)
Analisemos o que acontece as potências de 2 na aritmética módulo 3:
⟹ 2¹ = 2 ≡ 2 (mod 3)
⟹ 2² = 4 ≡ 1 (mod 3)
⟹ 2³ = 8 ≡ 2 (mod 3)
⟹ 2⁴ = 16 ≡ 1 (mod 8)
Observe que os restos seguem um padrão repetitivo e fácil de aprender. Usando esse padrão, podemos ver que:
[tex]\\ 2^{2k+1}~\equiv~2\pmod{3}\qquad\rm(i)\\\\\\ 2^{2k}~\equiv~1\pmod{3}\qquad\rm(ii)\\[/tex]
Vamos usar (i) e (ii) para encontrar a solução da nossa equação de congruência de maneira mais simples. Se fizermos uso de (i), temos que fazer n = 2k + 1, portanto, substituindo isso em nossa equação de congruência modular, temos:
[tex]\\ 2^n~\equiv~2n+1\pmod 3 \\\\\\ 2^{2k+1}~\equiv~2\cdot\left(2k+1\right)+1\pmod{3}\\\\\\ 2~\equiv~4k+2+1\pmod{3}\\\\\\ 0~\equiv~4k+1\pmod{3}\\\\\\ 4k+1~\equiv~0\pmod{3}\\\\\\ 4k~\equiv~-1\pmod3\\\\\\ 4k~\equiv~2\pmod3\\[/tex]
Da congruência anterior temos que o mdc(4, 3) = 1 e por definição 2 é divisível por 1, portanto existe solução. Se existe solução para a congruência anterior, existe um inteiro y, tal que:
[tex]\\ 4y~\equiv~1\pmod3\\\\\\ 4y~=~3t~+~1,\qquad com~t\in\mathbb{Z}\\[/tex]
O que acabamos de ter é uma equação diofantina, essa equação diofantina pode ser resolvida pelo algoritmo de Euclides, mas observe que não é complexa de resolver. Observe que se t = 1 podemos ver que:
[tex]\\4y~=~3\cdot1~+~1\\\\\\ 4y~=~4\\\\\\ \boxed{\sf y~=~1}\\[/tex]
Multiplicando o valor de y em ambas as partes da congruência original.
[tex]\\ \left(1\cdot4\right)k~\equiv~1\cdot2\pmod3\\\\\\ k~\equiv~2\pmod3\\\\\\ k~=~3q~+~2,\qquad\exists q\in\mathbb{N}\\[/tex]
O valor de k representa a solução desta equação de congruência modular, lembrando que n = 2k + 1 temos que n deve ser igual a:
[tex]\\ n~=~2\cdot\left(3q~+~2\right)~+~1\\\\\\ n~=~6q~+~4~+~1\\\\\\ {\boxed{\boxed{\bf n~=~6q~+~5}}},\qquad\exists q\in\mathbb{N}\\[/tex]
Para o caso (ii), temos que n = 2k se fizermos isso, podemos ver que nossa equação de congruência modular se torna:
[tex]\\ 2^n~\equiv~2n+1\pmod 3 \\\\\\ 2^{2k}~\equiv~2\cdot2k+1\pmod{3}\\\\\\ 1~\equiv~4k+1\pmod{3}\\\\\\ 0~\equiv~4k\pmod{3}\\\\\\ 4k~\equiv~0\pmod{3}\\\\\\ k~\equiv~0\pmod3\\\\\\\ k~=~3q,\qquad\exists q\in\mathbb{N}\\[/tex]
O valor de k representa a solução desta equação de congruência modular, lembrando que n = 2k temos que n deve ser igual a:
[tex]\\ n~=~2\cdot3q\\\\\\ \boxed{\boxed{\bf n~=~6q}},\qquad\exists q\in\mathbb{N}\\[/tex]
Combinando as duas soluções temos que n ∈ {6q + r: r ∈ {0, 5} e q ∈ ℕ}.