Euclidean Algorithm / arithmetic mod question

Question

I'm not sure how to approach this problem:

Solve for $x$.

$788x \equiv 24 (mod 1647)$.

I know that if 24 were replaced with 1, I could just do a backwards euclidean algorithm to find x. Can I still do the same thing?

Answer 1

Yes. Use the Euclidean algorithm to write something like $$ 1 = 788a + 1647b, $$ where $a,b \in \Bbb Z$. Then $$ 24 = 788(24a) + 1647(24b), $$ and taking everything modulo $1647$ should get you there.