Question

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

Answer 1

Primeiramente, pode se simplificar a congruência. Como o MDC(1164, 60, 3684) = 12, posso dividir todos os elementos da congruência por 12:
$1164x \equiv 60 \pmod {3684}\\97x \equiv 5 \pmod {307}$

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:
$97q \equiv 1 \pmod {307}\\97q - 307k = 1$

Equação diofantina que resolverei por meio do algoritmo de Euclides:
$307 = 97 \cdot 3 + 16\\97 = 16 \cdot 6 + 1$

Logo:
$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$

Para deixar no formato da expressão inicial:
$1 = 97 \cdot 19 - 307 \cdot 6$

Como uma das soluções da equação é $(q, k) = (19, 6)$, isso significa que $q = 19$, então este é um representante da classe inversa de 97, mod 307. Continuando na primeira das equações:

$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}$