Results 1 to 10 of 10

Math Help - More Congruence

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

    More Congruence

    if a\equiv b \ \mbox{(mod m)}, then a^2\equiv b^2 \ \mbox{(mod m)}

    Here is what I tried but it didn't go anywhere.

    m|(a-b)\rightarrow (mx)^2=(a-b)^2\rightarrow m^2x^2=a^2-2ab+b^2
    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 a\equiv b \ \mbox{(mod m)}, then a^2\equiv b^2 \ \mbox{(mod m)}

    Here is what I tried but it didn't go anywhere.

    m|(a-b)\rightarrow (mx)^2=(a-b)^2\rightarrow m^2x^2=a^2-2ab+b^2
    a \equiv b\ \Rightarrow aa \equiv ba\ \Rightarrow aa \equiv bb\ \Rightarrow a^2\equiv b^2\ (\text{mod}\ m).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    aa \equiv ba\ \Rightarrow aa \equiv bb .
    How does a turn into b?
    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
    How does a turn into b?
    MathWorld property #8.

    Let and , then

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    MathWorld property #8.

    Let and , then

    I don't see how that is justifying a=b
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by dwsmith View Post
    I don't see how that is justifying a=b
    I never wrote a=b. "a turning into b" is not the same as a=b, if you meant to convey this then you need to be more clear.

    All we need is ba \equiv bb.

    It's perhaps a little confusing since the letters overlap.

    Let's rewrite the mathworld property as follows

    Let x\equiv x' (mod m) and y \equiv y' (mod m), then

    xy \equiv x'y' (mod m)

    So here

    x=b
    x'=b
    y=a
    y'=b
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276

    An alternative

    dwsmith,

    An alternative, more along the lines of your original argument is take where you noted that if a\equiv{b}\,\pmod{m}, then m divides a-b; and then note that if m divides a-b, it divides (a-b)(a+b)=a^2-b^2, so a^2-b^2 is then a multiple of m as well.

    --Kevin C.
    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 TwistedOne151 View Post
    dwsmith,

    An alternative, more along the lines of your original argument is take where you noted that if a\equiv{b}\,\pmod{m}, then m divides a-b; and then note that if m divides a-b, it divides (a-b)(a+b)=a^2-b^2, so a^2-b^2 is then a multiple of m as well.

    --Kevin C.
    Why are we able to just to multiple (a+b) without multiplying the left side by (a+b)?
    Last edited by dwsmith; June 26th 2010 at 02:35 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Never mind, I have it.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    I like TwistedOne151's approach, but it's good to know what kinds of rules you can apply with congruences, which can make things easier in general, for example

    ab+cd\equiv a'b'+c'd'\ (\text{mod}\ n)

    as long as

    a\equiv a'\ (\text{mod}\ n)
    b\equiv b'\ (\text{mod}\ n)

    etc.

    This will help later on; for example, using Euler's theorem, you will be able to do this manipulation:

    a^{2\varphi(n)}\equiv \left(a^{\varphi(n)}\right)^2 \equiv 1^2 \equiv 1\ (\text{mod}\ n)

    given that gcd(a,n)=1.
    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, 11:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 02:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 06:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 10:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:57 AM

/mathhelpforum @mathhelpforum