$17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$. What are x and y?

Question

Congruency question: if $17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$, we need to find $x$ and $y$. There may be more than one answer. Not sure how to go about this; any help appreciated :)

Answer 1

Eliminate $x$ as follows:

$$13(17x+11y-7)-17(13x+10y-8)\equiv0\pmod{29}$$

$$\iff27y\equiv-45\pmod{29}$$

As $(29,3)=1$ $$\implies3y\equiv-5\iff y\equiv3^{-1}\cdot-5$$

As $3\cdot10-1\cdot29=1\implies3^{-1}\equiv10$

$$\implies y\equiv10\cdot-5\equiv8$$

Answer 2

Consider this a linear system over the field $\Bbb Z_{29}$. The determinat of the matrix is $17\cdot10-11\cdot13=170-143=27\neq 0$ because $29$ does not divide $27$. Then the sulution (mod $29$) is unique.

Now, the inverse of $17$ mod $29$ is $12$, since $17\cdot12=204=29\cdot 7+1$. So multiply the first equation by $12$ to obtain $$x-13y=-3$$

Then, apply Gaussian elimination in the usual way, but fon't forget that you are working in $\Bbb Z_{29}$.

Answer 3

By subtracting the two congruences you immediately get $4x+y \equiv -1 \pmod{29}$, i.e $$y\equiv -1-4x \pmod{29}.$$ Plug this into one of the original congruences. You will get a new congruence, which is linear and only has one unknown.

Solve this congruence. You should get $x\equiv9 \pmod{29}$.

And then use the above relation to find the corresponding $x$. You should get $y\equiv-8\equiv21\pmod{29}$.

You can check that this is indeed a solution of the given congruences: (17*9-11*8) mod 29=7 and (13*9-10*8) mod 29=8.