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