# Solve Modular Equation $5x \equiv 6 \bmod 4$

Here is an modular equation

$$5x \equiv 6 \bmod 4$$

And I can solve it, $x = 2$.

But what if each side of the above equation times 8, which looks like this

$$40x \equiv 48 \bmod 4$$

Apparently now, $x = 0$. Why is that? Am I not solving the modular equation in a right way, or should I divide both side with their greatest-common-divisor before solving it?

P.S.

To clarify, I was solving a system of modular equations, using Gaussian Elimination, and after applying the elimination on the coefficient matrix, the last row of the echelon-form matrix is :

$$0, \dots, 40 | 48$$

but I think each row in the echelon-form should have been divided by its greatest common divisor, that turns it into :

$$0, \dots, 5 | 6$$

But apparently they result into different solution, one is $x = 0,1,2,3....$, the other $x = 2$. And why? Am I applying Gaussian-Elimination wrong?

The congruence $40x\equiv48\pmod4$ means that $4\mid40x-48$. But $40x-48=4(10x-12)$, so this is always true: $40x\equiv48\pmod4$ for all integers $x$. Thus, $x\equiv0\pmod4$ is not the only solution.

Added: If you have the congruence $ax\equiv b\pmod m$, and $d$ is a common divisor of $a$ and $b$, you cannot simply divide through by $d$ and say that

$$\frac{a}dx\equiv\frac{b}d\!\!\!\!\pmod m\;;$$

it’s not generally true. However, if $d$ is a common divisor of $a,b$, and $m$, the original congruence is equivalent to the congruence

$$\frac{a}dx\equiv\frac{b}d\left(\bmod \frac{m}d\right)\;.$$

Here you can take $d=4$ to reduce the original problem to solving $10x\equiv12\pmod1$, and since all integers are congruent to one another mod $1$, you again arrive at the conclusion that $x$ can be any integer.

• So does it mean I shouldn't just simple times the original equation by 8? – avocado Jun 5 '13 at 1:22
• @loganecolss: No, you should not. In this case the easiest thing to do is probably what I did: go back to the definition. However, you can also divide through by the greatest common divisor of $40,48$, and $4$, which is $4$, to get the equivalent congruence $10x\equiv12\pmod1$. But any integers are congruent mod $1$, so every $x$ satisfies this congruence. – Brian M. Scott Jun 5 '13 at 1:25
• Well, you're right at this point, please see my POST, I edited it,. – avocado Jun 5 '13 at 1:30
• @loganecolss: It’s as I said in the addition to my answer: if you divide the coefficients by $d$, you must also divide the modulus by $d$. Since you did not do that, you replaced the congruence $40x\equiv48\pmod4$ with one that is not equivalent to it, i.e., that has a different set of solutions. – Brian M. Scott Jun 5 '13 at 1:34
• Well, now I think I should check my Gaussian-Elimination procedure. – avocado Jun 5 '13 at 1:36

Note that in multiplying each side of the original congruence by $8$, you multiplied the congruence by a multiple of the modulus, $4$, hence, since $4\mid 8$, both sides are thereby divisible by $4$, i.e., each side of the congruence is then a multiple of the modulus, and so congruent, by definition, to $0$. So the second congruence equation has an entirely different solution set.

If you had multiplied both sides of the original congruence by, say $3$, you would have maintained the solution set of $x$, $\text{mod}\;4$

• Yes, that makes sense. – avocado Jun 5 '13 at 1:35
• What if there are n variables in the system of congruence not just one, how to solve it? – avocado Jun 5 '13 at 8:27

Modular equivalence classes are multiplicative. Hence, since $40 \equiv 0 (\text{mod } 4)$ and $48 \equiv 0 (\text{mod } 4)$, all you've written there is $0\cdot x \equiv 0 (\text{mod } 4)$, which is true for any $x \in \mathbb{Z}/4\mathbb{Z}$ (the set of equivalence classes mod $4$). $x = 0$ is not the only "solution", but that's because as written the equation is effectively tautological - there is nothing to "solve" for.

• But If both sides divide by 8, then I can get x=2. These 2 equations are totally different? – avocado Jun 5 '13 at 1:23
• You have to be careful about what you're doing. Dividing by $8 (\text{mod } 4)$ is the same thing as dividing by $0 (\text{mod } 4)$, which isn't well defined! These two equations are different in the same way that the equations $4x + 4 = 18$ and $(4x+4)*0 = (18*0)$ are in the integers - you can't just go back and forth between them. Notice that the latter equation is true for all $x$ whereas the first certainly isn't! – Alex Wertheim Jun 5 '13 at 1:27
• Please see my POST, I just edited, add the reason why I did this. – avocado Jun 5 '13 at 1:31

Hint: mod $\,4\!:\,\ 40\equiv 0\equiv 48,\$ so $\,\ 40\cdot x\equiv 48\iff 0\cdot x\equiv 0,\$ true for all $\,x.$

Generally, scaling an equation by a noninvertible factor may increase the solution set.