Find all solutions of these linear congruences

Question

We have $(x,y) \in \mathbb{Z^2}$ and system

$6x + 3y \equiv 9 \mod 7$

$5x + 6y \equiv -3\mod 7$

How to calculate all possible $x$ and $y$?

My attempt was multiplying first equation and than subtracting second from it (I - II) and than I get:

$7x \equiv 21 \mod 7$

From here we can conclude that equation is valid for all $x \in \mathbb{Z}$.

Now I can take for example $x = 1$ and get solution for $y$ and it would be $y = 1$. Both values suits both equations but my solution is not complete. I believe that these are not only solutions, but how can I calculate rest of them?

Any suggestion is welcome.

Answer 1

Your manipulation shows that the two equations are equivalent, i.e. the first one is satisfied if and only if the second one is satisfied. So it is sufficient to find all solutions to the first equation. We can manipulate this to get $3y\equiv 9-6x$ (mod $7$), which, since $3$ is coprime to $7$, is the same as $y\equiv 3-2x$ (mod $7$). For any given $x$ the possible $y$ are given by $\{3-2x+7n\mid n\in\mathbb Z\}$, and so the set of solutions can be described as $\{(x,3-2x+7n)\mid x,n\in\mathbb Z\}$.

Answer 2

The determinant of your system is $0\mod 7$, and you can verify the fact by multiplying equation $1$ by $5$ and equation $2$ by $6$ : $$\left\{\begin{matrix} 30x+15y\equiv 45\,(7) \\ 30x+36y\equiv -18\,(7)\end{matrix}\right.\iff \left\{\begin{matrix} 2x+y\equiv 3\,(7) \\ 2x+y\equiv 3\,(7)\end{matrix}\right.$$ So you just have to solve one diophantine equation, which drives you back to previous lesson : $(1,1)$ is a solution, so the equation is equivalent to $2(x-1)+(y-1)\equiv 0\,(7)$. This means $$y-1=-2x+2+7k,\ k\in\mathbb Z \iff y=3-2x+7k,\ k\in\mathbb Z$$ So all the solutions are the couples $$(x,3-2x+7k),\ (x,k)\in\mathbb Z^2$$