Question

Resolver congruência linear 315x= 12(mod501)

Answer 1

Resposta:   $x\equiv 140~~\mathrm{(mod~}167),$

ou ainda, podemos escrever

     $\Longleftrightarrow\quad x=167n+140$

com n ∈ ℤ.

Explicação passo a passo:

Resolver a equação congruência linear

     $315x\equiv 12~~\mathrm{(mod~}501)$

Observamos que mdc(315, 12, 501) = 3, então a congruência acima pode ser simplificada por 3 e obtemos uma congruência equivalente à anterior. Essa é uma propriedade operatória válida para congruências modulares:

    $\Longleftrightarrow\quad 3\cdot (105x)\equiv 3\cdot (4)~~\mathrm{(mod~}3\cdot 167)\\\\ \Longleftrightarrow\quad 105x\equiv 4~~\mathrm{(mod~}167)\qquad\mathrm{(i)}$

O número 167 é primo, e 105 < 167. Portanto, mdc(105, 167) = 1, e sendo assim, existe algum inteiro y, tal que

     $105y\equiv 1~~\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad 105y=167k+1\\\\ \Longleftrightarrow\quad 105y-167k=1\qquad\mathrm{(ii)}$

para algum k inteiro.

(tal valor de y é por definição um representante da classe inversa do 105, módulo 167)

Vamos resolver a equação (ii) utilizando o algoritmo de Euclides (divisões sucessivas com quociente e resto):

     $167=105+62\\\\ 105=62+43\\\\ 62=43+19\\\\ 43=19\cdot 2+5\\\\ 19=5\cdot 3+4\\\\ 5=4+1$

Retornando no algoritmo, da última linha, temos

     $\Longleftrightarrow\quad 5-4=1$

Elimine o 4, substituindo-o por $19-5\cdot 3:$

     $\Longleftrightarrow\quad 5-(19-5\cdot 3)=1\\\\ \Longleftrightarrow\quad 5-19+5\cdot 3=1\\\\ \Longleftrightarrow\quad 19\cdot (-1)+5\cdot 4=1$

Elimine o 5, substituindo-o por $43-19\cdot 2:$

     $\Longleftrightarrow\quad 19\cdot (-1)+(43-19\cdot 2)\cdot 4=1\\\\ \Longleftrightarrow\quad 19\cdot (-1)+43\cdot 4+19\cdot (-8)=1\\\\ \Longleftrightarrow\quad 19\cdot (-1)+43\cdot 4+19\cdot (-8)=1\\\\ \Longleftrightarrow\quad 43\cdot 4+19\cdot (-9)=1$

Elimine o 19, substituindo-o por $62-43:$

     $\Longleftrightarrow\quad 43\cdot 4+(62-43)\cdot (-9)=1\\\\ \Longleftrightarrow\quad 43\cdot 4+62\cdot (-9)+43\cdot 9=1\\\\ \Longleftrightarrow\quad 62\cdot (-9)+43\cdot 13=1$

Elimine o 43, substituindo-o por $105-62:$

     $\Longleftrightarrow\quad 62\cdot (-9)+(105-62)\cdot 13=1\\\\ \Longleftrightarrow\quad 62\cdot (-9)+105\cdot 13+62\cdot (-13)=1\\\\ \Longleftrightarrow\quad 105\cdot 13+62\cdot (-22)=1$

Por fim, elimine o 62, substituindo-o por $167-105:$

     $\Longleftrightarrow\quad 105\cdot 13+(167-105)\cdot (-22)=1\\\\ \Longleftrightarrow\quad 105\cdot 13+167\cdot (-22)+105\cdot 22=1\\\\ \Longleftrightarrow\quad 105\cdot (35)-167\cdot (22)=1\qquad\mathrm{(iii)}$

Portanto, $y=35$ é uma solução para a equação (ii), ou seja,

     $105\cdot 35\equiv 1~~\mathrm{(mod~}167)\qquad\mathrm{(iv)}$

Dessa forma, para isolar o x, podemos multiplicar os dois membros da congruência (i) por y = 35:

     $\Longleftrightarrow\quad 35\cdot (105x)\equiv 35\cdot 4~~\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad (35\cdot 105)x\equiv 140~~\mathrm{(mod~}167)\\\\ \overset{\mathrm{(iv)}}{\Longleftrightarrow}\quad 1x\equiv 140~~\mathrm{(mod~}167)\\\\ \Longleftrightarrow\quad x\equiv 140~~\mathrm{(mod~}167)\quad\longleftarrow\quad\mathsf{resposta}$

ou ainda, podemos escrever

     $\Longleftrightarrow\quad x=167n+140$

com n ∈ ℤ.

Dúvidas? Comente.

Bons estudos! :-)