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

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

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}$.