Results 1 to 9 of 9

Math Help - Congruence

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    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)})
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    From
    Desert
    Posts
    28
    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 ).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by gosualite View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 10:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 10:57 AM

/mathhelpforum @mathhelpforum