Simulataneous equations

Question

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?

Answer 1

$$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)=?$$

Answer 2

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.

Answer 3

I would do the following (also available in PDF):

Answer 4

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