6
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So does it mean I shouldn't just simple times the original equation by 8? $\endgroup$ – avocado Jun 5 '13 at 1:22
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jun 5 '13 at 1:25
  • $\begingroup$ Well, you're right at this point, please see my POST, I edited it,. $\endgroup$ – avocado Jun 5 '13 at 1:30
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jun 5 '13 at 1:34
  • $\begingroup$ Well, now I think I should check my Gaussian-Elimination procedure. $\endgroup$ – avocado Jun 5 '13 at 1:36
3
$\begingroup$

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$

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

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.

$\endgroup$
  • $\begingroup$ But If both sides divide by 8, then I can get x=2. These 2 equations are totally different? $\endgroup$ – avocado Jun 5 '13 at 1:23
  • $\begingroup$ 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! $\endgroup$ – Alex Wertheim Jun 5 '13 at 1:27
  • $\begingroup$ Please see my POST, I just edited, add the reason why I did this. $\endgroup$ – avocado Jun 5 '13 at 1:31
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.