# System of congruent equations

Given the following system, how do you prove that there only is one solution congruent 8? $$3x+7y \equiv 2 (\text{mod } 8)$$ $$4x+5y \equiv 7 (\text{mod } 8)$$

My main idea have been to solve the equation, then to come to the solution that there only is one solution, however I get flawed results to say the least. Here is my method: $$\left\{ \begin{array}{ll} 3x+7y \equiv 2 (\text{mod } 8) \\4x+5y \equiv 7 (\text{mod } 8) \end{array} \right. \Leftrightarrow \left\{ \begin{array}{ll} 6x+14y \equiv 4 (\text{mod } 8) \\8x+10y \equiv 14 (\text{mod } 8) \end{array} \right. \Leftrightarrow \left\{ \begin{array}{ll} 6x+6y \equiv 4 (\text{mod } 8) \\2y \equiv 6 (\text{mod } 8) \end{array} \right.$$

$$\Leftrightarrow \left\{ \begin{array}{ll} 6x+18 \equiv 4 (\text{mod } 8) \\2y \equiv 6 (\text{mod } 8) \end{array} \right. \Leftrightarrow \left\{ \begin{array}{ll} -2x\equiv -14 (\text{mod } 8) \\2y \equiv 6 (\text{mod } 8) \end{array} \right. \Leftrightarrow \left\{ \begin{array}{ll} 2x\equiv 6 (\text{mod } 8) \\2y \equiv 6 (\text{mod } 8) \end{array} \right.$$

Which then gives: $$\left\{ \begin{array}{ll} x=4t+3 \\y=4s+3 \end{array} \right.$$ $t$ and $s$ being arbitary whole numbers

So solution given congruent 8 is: $$x\equiv 3 (\text{mod } 8) \text{ or } x\equiv 7 (\text{mod } 8)$$ $$y\equiv 3 (\text{mod } 8) \text{ or } y\equiv 7 (\text{mod } 8)$$ However when you put that into the original equation, the answer is wrong. So where did i do wrong...

• you cannot multiply by numbers not relatively prime with the modulo without losing equivalence. Have a look at this similar question : math.stackexchange.com/questions/2556129/…
– zwim
Commented Dec 19, 2017 at 21:20
• Doesnt that only count for division? Commented Dec 19, 2017 at 21:22
• You cannot divide by $0$ but would you multiply an equation by $0$ in a normal system ? This is the same in modular system when you multiply or divide by non invertible numbers. Instead here, substract line 1 to line 2 to express $x$ in function of $y$ and then substitute.
– zwim
Commented Dec 19, 2017 at 21:25
• Ahh, I get it now. Thanks! :) Commented Dec 19, 2017 at 21:27

Don't multiply equations by $2$: as $2$ is not coprime to $8$ you're not getting equivalent equations.

One way: given:

\begin{align}3x+7y\equiv 2 \pmod 8\\4x+5y\equiv 7\pmod 8\end{align}

Take away the 1st equation from the 2nd:

\begin{align}3x+7y\equiv 2 \pmod 8\\x-2y\equiv 5\pmod 8\end{align}

Take away 3 times the 2nd equation from the 1st one:

\begin{align}13y\equiv -13 \pmod 8\\x-2y\equiv 5\pmod 8\end{align}

Divide the first equation by $13$, which is coprime to $8$:

\begin{align}y\equiv -1 \pmod 8\\x-2y\equiv 5\pmod 8\end{align}

Add the first equation, multiplied by 2, to the 2nd:

\begin{align}y\equiv -1\equiv 7 \pmod 8\\x\equiv 3\pmod 8\end{align}

Bonus reading about what I've actually been (partially) doing to the equations: https://en.wikipedia.org/wiki/Smith_normal_form

$$4x+5y \equiv 7 (\text{mod } 8),$$ $$3x+7y \equiv 2 (\text{mod } 8).$$

Equation $1$ subtract equation $2$ $$4x+5y=7,$$ $$x+6y=5 \Rightarrow x=5-6y.$$ Substitute the second equation into the first one $$4(5-6y)+5y=7,$$ that is $$20-24y+5y=7 \Rightarrow 20-19y=7,$$ since we are in modulo $8$ $$4-3y=7 \Rightarrow -3y=3 \Rightarrow y=-1 = 7.$$ Then, substitute $y=7$ into equation $1$ $$4x+35=7 \Rightarrow4x=-28 \Rightarrow 4x=-4\ \text{or}\ 12 \Rightarrow x=-1\ \text{or}\ 3.$$

Inputting the $(x,y)$ pair $(-1,7)$ doesn't satisfy either of the two equations, so we may disregard this and are left with $$x=3,\quad y=7.$$

Probably very sloppy on notation, but I'm learning how to solve such systems in a number theory course myself so just thought I'd put my attempt in there.

• If x=1, y=7, then 3x+7y = 3+49 = 52 != 4, but it's supposed to equal 2. Your error was when you went from 4x = -28 to x = -7. Remember that 4 doesn't have an inverse in mod 8, so you can't divide both sides by 4. The equation 4x = -28 has two solutions: x = -1, x = 3. Commented Dec 19, 2017 at 22:00
• Ah I see, definitely something to bear in mind for future problems. Thank you very much. Commented Dec 19, 2017 at 22:05

Another method, that's specific to this question:

If x is even, then 4x is 0, so y = 3. Then 3x+21=2. The LHS is odd but the RHS is even, so "x is even" leads to a contradiction. So x is odd, 4x = 4, y =7, and x =3.

Write this linear system in matrix form: $$\begin{pmatrix}3&7\\4&5\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}\equiv\begin{pmatrix}2\\7\end{pmatrix}$$ and multiply both sides by the adjugate matrix, which is invertible mod. $8$: \begin{align} &\begin{pmatrix}5&1\\4&3\end{pmatrix}\begin{pmatrix}3&7\\4&5\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}\equiv\begin{pmatrix}5&1\\4&3\end{pmatrix}\begin{pmatrix}2\\7\end{pmatrix}\\[1ex] \iff &\begin{pmatrix}3&0\\0&3\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}\equiv\begin{pmatrix}1\\5\end{pmatrix}\\[1ex] \iff 3&\begin{pmatrix}3&0\\0&3\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}\equiv3\begin{pmatrix}1\\5\end{pmatrix}\\[1ex]\iff & \begin{pmatrix}1&0\\0&1\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}\color{red}x\\\color{red}y\end{pmatrix}\equiv\begin{pmatrix}\color{red}3\\\color{red}7\end{pmatrix}. \end{align}