Solving congruence system by deducting equations with one another

103 Views Asked by At

I need to get the general solution for the next congruence system $$3x+4y \equiv 2 \bmod 13\\ 2x+6y \equiv 1 \bmod 13$$ I have thought of multiplying one of the equations by some number and then deducting it from the other equation so one of the variables disappears but I can't think of the right way to solve the entire system.

2

There are 2 best solutions below

0
On BEST ANSWER

$$\begin{align} 3x+4y &\equiv 2 \bmod 13 \tag{1}\\ 2x+6y &\equiv 1 \bmod 13 \tag{2}\\ 10x+30y &\equiv 5 \bmod 13 \tag{3 [5$\times$(2)]}\\ 10x+4y &\equiv 5 \bmod 13 \tag{4}\\ 13x+8y &\equiv 7 \bmod 13 \tag{5 [(1)+(4)]}\\ 8y &\equiv 7 \bmod 13 \\ y &\equiv 9 \bmod 13 \tag{6}\\ \hline 2x+54 &\equiv 1 \bmod 13 \tag{7 [(6)$\to$(2)]}\\ 2x+2 &\equiv 1 \bmod 13 \\ 2x &\equiv 12 \bmod 13 \\ x &\equiv 6 \bmod 13 \\ \hline &\bigstar \end{align}$$

0
On

$$2(3x+4y)-3(2x+6y)\equiv2(2)-3(1)\pmod{13}$$

$$\iff-10y\equiv1\pmod{13}\iff3y\equiv1\iff y\equiv-4\equiv9$$ as $3(-4)\equiv1\pmod{13}\iff3^{-1}\equiv4$

$$3x+4y\equiv2\implies3x+4(9)\equiv2\iff3x\equiv-34\equiv5\iff x\equiv5(-4)\equiv-20\equiv6$$