Originally Posted by

**terrorsquid** I feel comfortable solving equations such as $\displaystyle xa + yb = c$ using Euclid's algorithm; however, I can't seem to see how I use this to solve congruence equations in the form: $\displaystyle ax \equiv c~ mod ~b$

What are the steps I need to take to solve something like (making this up):

$\displaystyle 7x \equiv 12~mod~27$

Also, how would I find an integer $\displaystyle m$ which is congruent to both

$\displaystyle 45~mod~1042$

and

$\displaystyle 53~mod~128$?

Also, I don't understand why there are no solutions if the modulo number is not prime (I was told that solving equations with non-prime modulo was out of the scope for my unit but I'm interested).