Simulataneous equations Suppose you have the following system of linear congruence
$2x+5y$ is congruent to 1 (mod6)
$x+y$ is congruent to 5 (mod6)
where $x,y \in \mathbb{Z}$ 
How would you obtain a general solution for this system. Also is there a way to determine whether the system is solvable or not? 
 A: The system
\begin{align*}
x+y & \equiv 5 \pmod{6}\\
2x+5y & \equiv 1 \pmod{6}
\end{align*}
can be rewritten as
$$
\begin{pmatrix}
1 & 1\\
2 & 5
\end{pmatrix}
\begin{pmatrix}
x\\y
\end{pmatrix}
\equiv \begin{pmatrix}
5\\1
\end{pmatrix} \pmod{6}
$$
Now consider using row-operations (modulo $6$ of course) to get
$$
\left[
\begin{array}{cc|c}
1 & 1 & 5\\
2 & 5 & 1\\
\end{array}
\right]
\longrightarrow \left[
\begin{array}{cc|c}
1 & 1 & 5\\
0 & 3 & 3\\
\end{array}
\right]
$$
The second congruence is $3y \equiv 3 \pmod{6}$. But $\gcd(3,6) \neq 1$ so you cannot simply cancel out $3$. However this gives us $y \equiv 1,3,5 \pmod{6}$. Now the first congruence gives
$$x \equiv 5-y \equiv 4, 2, 0 \pmod{6}.$$
Thus 
$$(x,y) \in \{(4,1), (2,3),(0,5)\} \subset \mathbb{Z}_6 \times \mathbb{Z}_6.$$
Remark: the solvability of such system of congruences $Ax \equiv b \pmod{n}$ is linked to the $\gcd(D, n)$, where $D=\text{det}A$. In particluar, if $\gcd=1$, then the system has a unique solution.
A: $$2x+5y=6a+1, x+y=6b+5$$ where $a,b$ are arbitrary integers
$$3y=2x+5y-2(x+y)=6a+1-2(6b+5)=3(2a-4b-3)$$
$$\iff y=2a-4b-3$$
$$2x+5y+(x+y)=6a+1+(6b+5)\iff x+2y=2a+2b+2$$
$$\iff x=2a+2b+2-2y=2a+2b+2-2(2a-4b-3)=?$$
A: I would do the following (also available in PDF):

A: All operations modulo 6:
$$
2x+5y \equiv 1 \longrightarrow 2x-y \equiv 1
$$
We can add that to $x+y \equiv 5$ to obtain
$$
3x \equiv 0
$$
meaning that $x$ must be even.  And then $y \equiv 5-x$.  This produces
$$
x \equiv 0, y \equiv 5
$$
$$
x \equiv 2, y \equiv 3
$$
$$
x \equiv 4, y \equiv 1
$$
