1. ## Congruence

if $ac\equiv bc \ \mbox{(mod m)}$, then $a\equiv b \ \mbox{(mod m)}$. $a,b,c\in\mathbb{Z} \ \mbox{and} \ m\in\mathbb{Z}^+$

$m|(ac-bc)\rightarrow mx=(a-b)c\rightarrow m\left(\frac{x}{c}\right)=(a-b)$

This false and only true if $c\neq 0$, correct?

2. Originally Posted by dwsmith
if $ac\equiv bc \ \mbox{(mod m)}$, then $a\equiv b \ \mbox{(mod m)}$. $a,b,c\in\mathbb{Z} \ \mbox{and} \ m\in\mathbb{Z}^+$

$m|(ac-bc)\rightarrow mx=(a-b)c\rightarrow m\left(\frac{x}{c}\right)=(a-b)$

This false and only true if $c\neq 0$, correct?
I think

$ac\equiv bc \ \mbox{(mod m)} \Rightarrow a\equiv b \ \mbox{(mod m)}$

is true if and only if $\displaystyle c$ has a multiplicative inverse mod m, in which case we can write

$ac\equiv bc \ \mbox{(mod m)} \Rightarrow acc^{-1}\equiv bcc^{-1} \ \mbox{(mod m)} \Rightarrow a\equiv b \ \mbox{(mod m)}$

Edit: Looking on MathWorld, property #12:

$ak \equiv bk\ (\text{mod}\ m)\Rightarrow a \equiv b\ (\text{mod}\ \frac{m}{\gcd(k,m)})$

3. Isn't what you are saying identical to what I said? Only true if $c\neq 0$ since there is no $0^{-1}$ because division by 0 is undefined.

4. Originally Posted by dwsmith
Isn't what you are saying identical to what I said? Only true if $c\neq 0$ since there is no $0^{-1}$ because division by 0 is undefined.
They're different. For example, 3 does not have a multiplicative inverse mod 6.

5. But $2\cdot 3 \equiv 4 \cdot 3 \mod 6$, but $2 \not\equiv 3 \mod 6$, so you cannot cancel the 3 in this case (elaborating undefined's example). You can only cancel numbers that are relatively prime to the mod ( i.e. when $\gcd(c,m) = 1$ ).

6. Originally Posted by gosualite
But $2\cdot 3 \equiv 4 \cdot 3 \mod 6$, but $2 \not\equiv 3 \mod 6$, so you cannot cancel the 3 in this case. You can only cancel numbers that are relatively prime to the mod ( i.e. when $\gcd(c,m) = 1$ ).
Your 3 should be a 4 in the example but I understand what you are saying.

7. Originally Posted by dwsmith
Your 3 should be a 4 in the example but I understand what you are saying.
No, my 3 should be a 3. As it happens, 4 also does not have a multiplicative inverse mod 6. In general, "a" has a multiplicative inverse mod n if and only if gcd(a,n)=1.

Edit: Sorry got a bit confused with everyone posting at the same time, thought the OP was responding to my post. Carry on.

8. Originally Posted by undefined
No, my 3 should be a 3. As it happens, 4 also does not have a multiplicative inverse mod 6. In general, "a" has a multiplicative inverse mod n if and only if gcd(a,n)=1.
That last reply wasn't in regards to you. In gosualite, reply there is $2\not\equiv 3 \ \mbox{but it should say} \ 2\not\equiv 4$

9. Originally Posted by dwsmith
That last reply wasn't in regards to you. In gosualite, reply there is $2\not\equiv 3 \ \mbox{but it should say} \ 2\not\equiv 4$
No problem, I noticed that a bit late and edited my other post.