system of conguences

Question

I am trying to figure out how to solve:

Find $x, y \in \mathbb{Z}$ such that $$2x+y\equiv 4\pmod{17}$$ and $$5x-5y\equiv 9\pmod{17}.$$

I know this means $2x+y-4$ and $5x-5y-9$ are multiples of $17$, but I can't figure out how to solve the problem from there.

Thanks for your help!

Answer 1

$y\equiv4-2x\pmod{17}\ \ \ \ (1)$

$$5x-5y\equiv5x-5(4-2x)\equiv15x-20$$ So, $15x-20\equiv9\pmod{17}\iff15x\equiv29\equiv12\pmod{17}$

As $(17,3)=1,$ $$5x\equiv4\pmod{17}\equiv4-34$$

As $(17,5)=1,$ $$x\equiv-6\equiv11$$

Now use $(1),$ to find $y$

Answer 2

Algebraically you can manipulate congruences pretty much like you can manipulate equations. So solving a system of congruences can be approached much like solving a system of equations.

So for instance for this one, you could solve for $y$ in the first congruence and then substitute for $y$ in the second (substitution method), leaving you with a congruence in one variable to solve.

Or you could multiply the first congruence by $5$ and add it to the second to eliminate $y$, again resulting in a congruence in one variable.

Answer 3

From the first you get $y\equiv 4 -2x \pmod{17}.$ Substitute into the second you have $$5x -5(4-2x) \equiv 9 \pmod {17} \Longrightarrow 15x \equiv 29 \pmod {17}$$ Therefore $$x\equiv 29\times 15^{-1} \equiv 29\times 8 \equiv 11 \pmod {17}$$ and $$y \equiv 4 -22 \equiv 16 \pmod {17}$$ Check the solution!