Question

Resolver a congruência linear 1164x=60(mod 3684)

Answer 1

Resposta:   $x\equiv 95\pmod{307},$

ou ainda, podemos escrever

     $\Longleftrightarrow\quad x=307n+95$

com n ∈ ℤ.

Explicação passo a passo:

Resolver a equação congruência linear

     $1164x\equiv 60\pmod{3684}$

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

    $\Longleftrightarrow\quad 12\cdot (97x)\equiv 12\cdot (5) \pmod{12\cdot 307}\\\\ \Longleftrightarrow\quad 97x\equiv 5\pmod{307}\qquad\mathrm{(i)}$

Os números 97 e 307 são primos, portanto, mdc(97, 307) = 1, e sendo assim, existe algum inteiro y, tal que

     $97y\equiv 1\pmod{307}\\\\ \Longleftrightarrow\quad 97y=307k+1\\\\ \Longleftrightarrow\quad 97y-307k=1\qquad\mathrm{(ii)}$

para algum k inteiro.

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

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

     $307=97\cdot 3+16\\\\ 97=16\cdot 6+1$

Retornando no algoritmo, da última linha, temos

     $\Longleftrightarrow\quad 97-16\cdot 6=1$

Elimine o 16, substituindo-o por $307-97\cdot 3:$

     $\Longleftrightarrow\quad 97-(307-97\cdot 3)\cdot 6=1\\\\ \Longleftrightarrow\quad 97+307\cdot (-6)+97\cdot 18=1\\\\ \Longleftrightarrow\quad 97\cdot (19)-307\cdot (6)=1\qquad\mathrm{(iii)}$

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

     $97\cdot 19\equiv 1\pmod{307}\qquad\mathrm{(iv)}$

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

     $\Longleftrightarrow\quad 19\cdot (97x)\equiv 19\cdot 5\pmod{307}\\\\ \Longleftrightarrow\quad (19\cdot 97)x\equiv 95\pmod{307}\\\\ \overset{\mathrm{(iv)}}{\Longleftrightarrow}\quad 1x\equiv 95\pmod{307}\\\\ \Longleftrightarrow\quad x\equiv 95\pmod{307}\quad\longleftarrow\quad\mathsf{resposta}$

ou ainda, podemos escrever

     $\Longleftrightarrow\quad x=307n+95$

com n ∈ ℤ.

Dúvidas? Comente.

Bons estudos! :-)