Primeiramente, pode se simplificar a congruência. Como o MDC(1164, 60, 3684) = 12, posso dividir todos os elementos da congruência por 12: [tex]1164x \equiv 60 \pmod {3684}\\97x \equiv 5 \pmod {307}[/tex]
Agora, para isolar a incógnita, basta multiplicá-la por algum representante da classe inversa de 97, mod 307, já que este produto pode ser simplificado para 1. Sabe-se que existe uma classe inversa pois MDC(97, 307) = 1. Sendo q este representante, temos que: [tex]97q \equiv 1 \pmod {307}\\97q - 307k = 1[/tex]
Equação diofantina que resolverei por meio do algoritmo de Euclides: [tex]307 = 97 \cdot 3 + 16\\97 = 16 \cdot 6 + 1[/tex]
Para deixar no formato da expressão inicial: [tex]1 = 97 \cdot 19 - 307 \cdot 6[/tex]
Como uma das soluções da equação é [tex](q, k) = (19, 6)[/tex], isso significa que [tex]q = 19[/tex], então este é um representante da classe inversa de 97, mod 307. Continuando na primeira das equações:
Lista de comentários
Primeiramente, pode se simplificar a congruência. Como o MDC(1164, 60, 3684) = 12, posso dividir todos os elementos da congruência por 12:
[tex]1164x \equiv 60 \pmod {3684}\\97x \equiv 5 \pmod {307}[/tex]
Agora, para isolar a incógnita, basta multiplicá-la por algum representante da classe inversa de 97, mod 307, já que este produto pode ser simplificado para 1. Sabe-se que existe uma classe inversa pois MDC(97, 307) = 1. Sendo q este representante, temos que:
[tex]97q \equiv 1 \pmod {307}\\97q - 307k = 1[/tex]
Equação diofantina que resolverei por meio do algoritmo de Euclides:
[tex]307 = 97 \cdot 3 + 16\\97 = 16 \cdot 6 + 1[/tex]
Logo:
[tex]1 = 97 - 16 \cdot 6\\1 = 97 - (307 - 97 \cdot 3) \cdot 6\\1 = 97 - (6 \cdot 307 - 18 \cdot 97)\\1 = 97 - 6 \cdot 307 + 18 \cdot 97\\1 = -6 \cdot 307 + 19 \cdot 97[/tex]
Para deixar no formato da expressão inicial:
[tex]1 = 97 \cdot 19 - 307 \cdot 6[/tex]
Como uma das soluções da equação é [tex](q, k) = (19, 6)[/tex], isso significa que [tex]q = 19[/tex], então este é um representante da classe inversa de 97, mod 307. Continuando na primeira das equações:
[tex]97x \equiv 5 \pmod {307}\\19(97x) \equiv 19 \cdot 5 \pmod {307}\\1843x \equiv 95 \pmod {307}\\307 \cdot 6x + x \equiv 95 \pmod {307}\\x \equiv 95 \pmod {307}[/tex]