Question

Resolver os seguintes sistemas de congruências lineares usando o Teorema Chinês dos Restos
a) x ≡ 1 (mod 5 )
x ≡ 2 (mod 7 )
x ≡ 3 (mod 11)
b) x ≡1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 5 (mod 7)

Answer 1

Resposta:

a) $x=385n+366,\qquad\mathrm{com~}n\in\mathbb{Z}.$

b) $x=42n+5,\qquad\mathrm{com~}n\in\mathbb{Z}.$

Explicação passo a passo:

Resolver os sistemas de congruências lineares utilizando o Teorema Chinês dos Restos.

O Teorema Chinês dos Restos afirma que, dados $a_1,\,a_2,\,\cdots,\, a_k\in\mathbb{N}^{*}$ e $m_1,\,m_2,\,\cdots,\,m_k\in\mathbb{N}^{*}$ com $\mathrm{mdc}(m_i,\,m_j)=1$ para $i\ne j,$ o sistema de congruências lineares

    $\left\{\begin{array}{l} x\equiv a_1\quad(\mathrm{mod~}m_1)\\ x\equiv a_2\quad(\mathrm{mod~}m_2)\\ \vdots\\ x\equiv a_k\quad(\mathrm{mod~}m_k)\end{array}\right.$

possui solução única módulo $(m_1\cdot m_2\cdot \ldots\cdot m_k)$, e tal solução é dada por

    $x\equiv a_1\cdot M_1\cdot x_1+a_2\cdot M_2\cdot x_2+\cdots +a_k\cdot M_k\cdot x_k\quad (\mathrm{mod~} \prod_{i=1}^k m_i)$

sendo

    $M_j=\dfrac{m_1\cdot m_2\cdot \ldots\cdot m_k}{m_j}=\dfrac{\prod_{i=1}^k m_i}{m_j}\qquad \mathrm{com~}j\in\{1,\,2,\,\cdots,\,k\}$

e cada $x_j$ é um representante da classe inversa de $M_j$ módulo $m_j,$ isto é,

    $x_j\cdot M_j\equiv 1\qquad(\mathrm{mod~}m_j),\qquad j\in\{1,\,2,\,\cdots,\,k\}.$

a)

    $\left\{\begin{array}{l}x\equiv 1\quad(\mathrm{mod~}5)\\ x\equiv 2\quad(\mathrm{mod~}7)\\x\equiv 3\quad(\mathrm{mod~}11) \end{array}\right.$

Escrevendo em uma tabela os valores que precisamos para calcular a solução:

    $\begin{array}{|c|c|c|c|c|c|}&a_j&m_j&M_j&x_j&a_j\cdot M_j\cdot x_j \\&&&&&\\ j=1:&\mathbf{1}&5&\mathbf{77}\equiv 2~(\mathrm{mod~}5)&2^{-1}\equiv \mathbf{3}~(\mathrm{mod~}5)&\mathbf{1\cdot 77\cdot 3=231}\\ j=2:&\mathbf{2}&7&\mathbf{55}\equiv 6~(\mathrm{mod~}7)&6^{-1}\equiv \mathbf{6}~(\mathrm{mod~}7)~&\mathbf{2\cdot 55\cdot 6=660}\\ j=3:&\mathbf{3}&11&\mathbf{35}\equiv 2~(\mathrm{mod~}11)&2^{-1}\equiv \mathbf{6}~(\mathrm{mod~}11)&\mathbf{3\cdot 35\cdot 6=630}\end{array}$

Somando a última coluna, a solução é

    $x\equiv 231+660+630\quad(\mathrm{mod~}5\cdot 7\cdot 11)\\\\ x\equiv 1521\quad(\mathrm{mod~}385)\\\\x\equiv 366\quad(\mathrm{mod~}385)\\\\x=385n+366\qquad\mathrm{com~}n\in\mathbb{Z}.\quad$

b)

    $\begin{array}{|c|c|c|c|c|c|}&a_j&m_j&M_j&x_j&a_j\cdot M_j\cdot x_j \\&&&&&\\ j=1:&\mathbf{1}&2&\mathbf{21}\equiv 1~(\mathrm{mod~}2)&1^{-1}\equiv \mathbf{1}~(\mathrm{mod~}2)&\mathbf{1\cdot 21\cdot 1=21}\\ j=2:&\mathbf{2}&3&\mathbf{14}\equiv 2~(\mathrm{mod~}3)&2^{-1}\equiv \mathbf{2}~(\mathrm{mod~}3)~&\mathbf{2\cdot 14\cdot 2=56}\\ j=3:&\mathbf{5}&7&\mathbf{6}\equiv 6~(\mathrm{mod~}7)&6^{-1}\equiv \mathbf{6}~(\mathrm{mod~}7)&\mathbf{5\cdot 6\cdot 6=180}\end{array}$

Somando a última coluna, a solução é

    $x\equiv 21+56+180\quad(\mathrm{mod~}2\cdot 3\cdot 7)\\\\ x\equiv 257\quad(\mathrm{mod~}42)\\\\x\equiv 5\quad(\mathrm{mod~}42)\\\\x=42n+5\qquad\mathrm{com~}n\in\mathbb{Z}.\quad$

Bons estudos!