Solve $561x \equiv 3575 \pmod{1562}$ for $x$. I was able to get as far as 
$561x - 3575 = 1562y$
But now I cannot figure out how to get an integer solution for $x$.
Any help is appreciated, thanks. 
 A: Dividing everything by 11, you get
$$51x = 325 = 41 \pmod{142}.$$
(This is permissible because $11k | 11l$ if and only if $k|l$.) 
Now 51 and 142 are relatively prime. Use Euclid's method to find and inverse of 51 modulo 142. Then multiply both sides of the equation by the inverse to obtain an equivalent equation modulo 142.
A: For a linear congruence of the form: $$ax \equiv b \mod m,$$ we have that if $gcd(a,m)|b,$ there are $d=gcd(a,m)$ solutions modulo $m.$ The solutions are of the form $$x=x_0+\frac{m}{d}t,$$ where $x_0$ is a particular solution.
In order to find the particular solution for your problem, we will use the extended euclidean algorithm to represent $gcd(561,1562)$ as a linear combination of $561$ and $1562$:
(note that this is carried out for instructional purposes and on when you are doing it yourself you should divide everything by $11$ to reduce the calculation considerably)
\begin{array}{|c|c|c|}
\hline
1562&  & 39  \\ \hline
 561&2 & 14\\ \hline
440 &1  & 11\\ \hline
121 & 3 & 3\\ \hline
77 & 1 & 2\\ \hline
44 & 1 & 1\\ \hline
33 & 1 & 1\\ \hline
11 & 3 & 0\\ \hline
0 & & \hline
\end{array}
From this table we see that $11=gcd(561,1562)$ and also that: $$561(39)+1562(-14)=11,$$ Which means that:
$$561(39)(325)+1562(-14)(325)=11(325)=3575.$$ So $x_0=39 \times 325=12675 $ and we find that the solution to the linear congruence is given as:
$$x=12675+325t.$$
