Question

Solve the congruence 169x 25 (mod 330)

Answer 1

First solve the congruence $13y\equiv1\pmod{330}$. Euclid's algorithm shows

330 = 25 * 13 + 5

13 = 2 * 5 + 3

5 = 1 * 3 + 2

3 = 1 * 2 + 1

=> 1 = 127 * 13 - 5 * 330

=> 127 * 13 = 1 mod 330

so that $y=127$ is the inverse of 13 modulo 330. Then in the original congruence, multiplying both sides by 127 twice gives

$127^2\cdot13^2x\equiv127^2\cdot5^2\pmod{330}\implies x\equiv127^2\cdot5^2\equiv403,225\equiv295\pmod{330}$

Then any integer of the form $x=295+330n$ is a solution to the congruence, where $n$ is any integer.