Results 1 to 9 of 9

Thread: Congruence

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

    Congruence

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

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

    This false and only true if $\displaystyle 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 $\displaystyle ac\equiv bc \ \mbox{(mod m)}$, then $\displaystyle a\equiv b \ \mbox{(mod m)}$. $\displaystyle a,b,c\in\mathbb{Z} \ \mbox{and} \ m\in\mathbb{Z}^+$

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

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

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

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

    $\displaystyle 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:

    $\displaystyle 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
    10
    Isn't what you are saying identical to what I said? Only true if $\displaystyle c\neq 0$ since there is no $\displaystyle 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 $\displaystyle c\neq 0$ since there is no $\displaystyle 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 $\displaystyle 2\cdot 3 \equiv 4 \cdot 3 \mod 6$, but $\displaystyle 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 $\displaystyle \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
    10
    Quote Originally Posted by gosualite View Post
    But $\displaystyle 2\cdot 3 \equiv 4 \cdot 3 \mod 6$, but $\displaystyle 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 $\displaystyle \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
    10
    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 $\displaystyle 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 $\displaystyle 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: Nov 10th 2008, 01:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 30th 2008, 05:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 30th 2008, 09:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 10:57 AM

/mathhelpforum @mathhelpforum