Solve the linear congruences (find the general solution or prove that no solution exists)

Question

I am a bit stuck on these questions. It will be grateful if someone can help figure it out.

1. $67x \equiv 282 \pmod{283}$
2. $737x \equiv 1727 \pmod{2002}$

Do I need to use the Euclidean algorithm to solve it first? Then get $\gcd = 1$?

Answer 1

So, let's look at that first problem: $$ 67x \equiv -1 \pmod{283} $$ So, first thing's first: go through the Euclidean algorithm: $$ 283 = 4(67) + 15\\ 67 = 4(15) + 7\\ 15 = 2(7) + 1 $$ Now, solve these equalities for the remainder $$ 1 = 15 - 2(7)\\ 7 = 67 - 4(15)\\ 15 = 283 - 4(67) $$ Now, substitute into the first in order to get a linear combination of our two numbers that yields $1$ $$ \begin{align} 1 &= 15-2(7) = 1\\ &= 15 - 2(67 - 4(15)) = 9(15) - 2(67)\\ &= 9(283 - 4(67)) - 2(67) = 9(283) - 38(67) \end{align} $$ Now that we know that $9(283) - 38(67) = 1$, we can conclude that $(-38)67 \equiv 1 \pmod {283}$. Multiplying both sides by $-1$, we find $(38)67 \equiv -1 \pmod{283}$.