Can't find error in my modular arithmetic

[Eternals]

Homework Statement

Solve the equation, if a solution exists:
3x = 4 (mod 6)

Homework Equations

If a = c (mod m), b = d (mod m), then:
a * b = c * d (mod m)

The Attempt at a Solution

There is no solution, because 3x will always result in 0 or 3 for all integers x.

However, what I don't understand is this:
Multiplying both sides of 3x = 4 (mod 6) by 3:
9x = 12 (mod 6)
9x = 0 (mod 6)

So the above equation now has solutions 0, 2, 4, 6, ..., but the answer should be no solution. What step did I do wrong in the modular arithmetic?

 

[Hurkyl]

So the above equation now has solutions 0, 2, 4, 6, ..., but the answer should be no solution. What step did I do wrong in the modular arithmetic?

You didn't do anything wrong with the arithmetic. The problem is your logic -- you have your implications backwards. Every solution to the original equation is a solution to your new equation, not the other way around.


It's easy to make the same mistake even without the modular arithmetic. What are integer solutions to 2x = 3? Now if we multiply both sides by zero, what are the integer solutions to 0x = 0?

 

[Robert1986]

Homework Statement

Solve the equation, if a solution exists:
3x = 4 (mod 6)

Homework Equations

If a = c (mod m), b = d (mod m), then:
a * b = c * d (mod m)

The Attempt at a Solution

There is no solution, because 3x will always result in 0 or 3 for all integers x.

However, what I don't understand is this:
Multiplying both sides of 3x = 4 (mod 6) by 3:
9x = 12 (mod 6)
9x = 0 (mod 6)

So the above equation now has solutions 0, 2, 4, 6, ..., but the answer should be no solution. What step did I do wrong in the modular arithmetic?

What do you mean by the above equation has even integers as a solution?

3*0 = 0 mod 6
3*2 = 0 mod 6
3*4 = 0 mod 6
3*6 = 0 mod 6

and on.

Those are not solutions to the equation 3x = 4 mod 6. To solve a problem like this, you need to find the (additive) inverse of 3 (mod 6). However, there isn't one. Let's on the other hand, say that the equation is:

$$3x \equiv 4 (mod 5)$$

Then 3*2 = 6 = 1 (mod 5). So, you would multiply both sides of the equation by 2 that is:

$$2*3x = 2*4 (mod 5) \Rightarrow$$
$$x \equiv 3 (mod 5)$$

Therefore, 3 (mod 5) is a solution. For example, 23 is 3 (mod 6). 3*23 = 69 = 4 (mod 5).

 

[Eternals]

Thanks a lot for your replies! I think I understand this better now. I have a few more questions left:

1) If I understood correctly, multiplying both sides does not always lead to equivalent statements. So, when do you know if the implications can go in both directions?
2) Do you always have to multiply by the multiplicative inverse to solve this? For example, 4x = 2 (mod 6). Then 4 has no multiplicative inverse, but there are still some solutions to x, for example x = 2.

 

[Robert1986]

Thanks a lot for your replies! I think I understand this better now. I have a few more questions left:

1) If I understood correctly, multiplying both sides does not always lead to equivalent statements. So, when do you know if the implications can go in both directions?
2) Do you always have to multiply by the multiplicative inverse to solve this? For example, 4x = 2 (mod 6). Then 4 has no multiplicative inverse, but there are still some solutions to x, for example x = 2.

1) Multiplying both sides by the same number (in fact, they just have to be conrguent modulo the modulus) will always lead to equivalent statements.

2) Consider the congruence : ax = b (mod m)

Let gcd(a,m) = d. If d does not divide b, then there are no solutions. If d does divide b, then there are d incongruent solutions.

So, the equation 3x = 4 (mod 6) a = 3, m = 6, so gcd(a,m) = 3. But 3 does not divide b=4.
On the other hand 4x =2 (mod6) gcd(a,m) = gcd(4,6)=2 which does divide 2. So, there is actually one more incongruent solution: 3.

 

[Hurkyl]

Thanks a lot for your replies! I think I understand this better now. I have a few more questions left:

1) If I understood correctly, multiplying both sides does not always lead to equivalent statements. So, when do you know if the implications can go in both directions?

It will always be true when the transformation is invertible -- in this case, when the number has an inverse you can multiply by.

With modular arithmetic, you can often make the transform invertible by adjusting the modulus, though I'd have to do some work to figure out what adjustments are valid.

Robert1986, I think, thought you were asking a different question than you really were -- the question of "if the LHS and RHS really are equal in the original statement, will they also be equal in the new statement?"

2) Do you always have to multiply by the multiplicative inverse to solve this? For example, 4x = 2 (mod 6). Then 4 has no multiplicative inverse, but there are still some solutions to x, for example x = 2.

Again I'd have to do a bit of work to remind myself, but I think that if d divides the modulus and both the LHS and RHS (when viewed as equations of integers), then you get an equivalent statement by dividing all three of the L.H.S., the R.H.S., and the modulus by d.

Also, a standard approach to solving modular equations is to split it into primary parts -- in this case look at the equation modulo 2 and modulo 3, then use the Chinese Remainder problem to reassemble the solution.

In case there's a prime power (e.g. modulo 4), it usually isn't hard to solve things modulo 2, then use that to work out the solutions modulo 4, then modulo 8, and so forth. A systematic approach exists via "Hensel's Lemma" and/or using p-adic analysis.