Problem with solving systems of linear congruence of two variables

Question

The problem I am given is finding a solution to the following pair of equations:

$3x + 4y$ $\equiv$ $5$ $mod$ $13$

$2x + 5y$ $\equiv$ $7$ $mod$ $13$

By reading the methodology here: How do you solve linear congruences with two variables.

Since the modulos in my problem are also the same, I am able to use substitution, but this leaves fractions in my expressions.

I then used matrix multiplication as follows:

$\begin{bmatrix} 3 & 4\\ 2 & 5\end{bmatrix}$ $\begin{bmatrix}\ x\\ y\end{bmatrix}$ = $\begin{bmatrix}\ 5\\ 7\end{bmatrix}$

And solving this also gives me a matrix with fractions, so I am a bit lost on how to solve this problem.

Any help is appreciated. Thank you very much.

Answer 1

We have $3x + 4y \equiv 5\pmod{13}$. Since $(8,13)=1$ we can multiply $8$ on both sides of the above congruence. This yields , $$24x+32y\equiv 40\pmod{13}$$ $$\implies -2x+6y\equiv 1\pmod {13}$$ Now adding the above equation with $2x + 5y \equiv7 \pmod{13}$ we get $$11y\equiv 8\pmod{13}$$. The above congruence has a solution $y=9$. Substituting this in any one of the above equations will give you $x=7$. So $x=7$ and $y=9$ satisfies the given system of equations.

Answer 2

Cramer's Rule works since the determinant $= 7\,$ is invertible, being coprime to the modulus $13$

$$\begin{align} \left[\begin{matrix} 5 &\!\!\! -4 \\ -2 &\! 3 \end{matrix}\right]\ \times\ &\left\{\, \left[\begin{matrix} 3 & 4 \\ 2 & 5 \end{matrix}\right] \left[\begin{matrix} x \\ y \end{matrix}\right] \equiv \left[\begin{matrix} 5 \\ 7 \end{matrix}\right]\,\right\}\pmod{\!13}\\[.8em] \Longrightarrow &\ \ \ \left[\begin{matrix} 7 & 0 \\ 0 & 7 \end{matrix}\right] \left[\begin{matrix} x \\ y \end{matrix}\right] \equiv \left[\begin{matrix} 10 \\ 11 \end{matrix}\right] \end{align}\qquad$$

$$\begin{align}{\rm Therefore}\ \ \ &7x\equiv 10 \iff x\equiv \dfrac{10}7\equiv \dfrac{20}{14}\equiv \dfrac{7}1\\[.5em] &7y\equiv\ 11 \iff y\equiv \dfrac{11}7\equiv \dfrac{22}{14}\equiv \dfrac{9}1\end{align}\!\! $$