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.


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.