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.