Results 1 to 6 of 6

Math Help - congruence and the Division Algorithm...

  1. #1
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Post congruence and the Division Algorithm...

    Disprove with the counter example: If a^2 = b^2 (mod n) then a=b (mod n)..
    where "=" means the equivalence.

    I think...since, n\a^2 - b^2...proceeds to n\(a-b)(a+b)...shows that n also divides (a-b)...so can't we directly say that a=b (mod n)..??

    how do I do this one?

    Thanks for any help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Vedicmaths View Post
    Disprove with the counter example: If a^2 = b^2 (mod n) then a=b (mod n)..
    where "=" means the equivalence.

    I think...since, n\a^2 - b^2...proceeds to n\(a-b)(a+b)...shows that n also divides (a-b)...so can't we directly say that a=b (mod n)..??

    how do I do this one?

    Thanks for any help!
    1^2 \equiv (-1)^2 (\bmod 3).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Vedicmaths View Post
    Disprove with the counter example: If a^2 = b^2 (mod n) then a=b (mod n)..
    where "=" means the equivalence.

    I think...since, n\a^2 - b^2...proceeds to n\(a-b)(a+b)...shows that n also divides (a-b)...so can't we directly say that a=b (mod n)..??

    how do I do this one?

    Thanks for any help!
    The part I have marked in red is wrong.

    Its a nice question...

    if n|(a^2 - b^2), n need not necessarily divide a-b but it could divide a+b. Consider n = 5 and a = 4 and b = 1...

    In fact n need not divide both a-b and a+b! As an example choose n = 8, a = 3,b=1...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Post

    I got until this part:

    n divides a^2 - b^2 then we could say for some k, (a-b)(a+b) = nk..now similarly for some l , a+b = nl..

    so dividing both of these equations we get: (a-b) = k/l...and I am stuck after this part! is this a right way to proceed??
    please help!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Post a little head up!

    well I tried disproving it and got this one. Like you said, just need one example where ti does not work...

    For example, a = 7, b = 2, N = 3.

    7^2 mod 3 = 1
    2^2 mod 3 = 1
    so 7^2 mod 3 = 2^2 mod 3

    BUT
    7 mod 3 = 1
    2 mod 3 = 2
    so 7 mod 3 != 2 mod 3

    So it satisfies our counterexample....but I still don't understand, how do we know that any conditions like this one, proves or disproves? so do we always look for disproving first and pick any examples where it does not work. Or something else?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Didnt you follow my reasoning? Its clear from that...

    n|a^2-b^2 = (a-b)(a+b)

    Now I realised that if n|(a+b) then n|(a^2 - b^2).... This is how I figured n need not divide a-b.

    Now to disprove choose n = a+b for some n,a,b
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 12:51 PM
  2. Euclidan Algorithm linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 9th 2009, 11:35 AM
  3. Abstract Algebra: Congruence and The Division Algorithm 1
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 18th 2008, 11:13 AM
  4. Replies: 2
    Last Post: February 16th 2008, 02:30 PM
  5. division algorithm
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: September 7th 2007, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum