Results 1 to 3 of 3

Math Help - congruence and gcd

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    84

    Question congruence and gcd

    Can anyone please help me with this proof?

    if ab≡0(mod n), then shows that gcd⁡(a,n)∙gcd⁡(b,n)=n.

    Any suggestions will be very appreciate.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2008
    Posts
    10
    denise,

    This is a standard problem in elementary number theory. I'll provide you with my general approach but I'll leave some details up to you.

    First given the nature of what we want to prove, we infer that n is a postive integer. Let d = gcd(a,n) and e = gcd(b,n). We show that de|n and n|de (Recall a|b denotes a divides b). Now clearly since d|a and e|b, it follows that de|ab. Now as gcd(ab,n) = n (why? because ab = 0 (mod n)), we have de|n.

    To show that n|de, we use another property of gcd. Recall by Bezout's theorem that there exist integers x and y such that gcd(a,b) = ax + by. So apply this to d and e and you will see that since ab = 0 (mod n), it follows that n|de.

    I hope this is of some help to you. Feel free to give me reps (whatever that is) Good Luck!

    Best,

    m_s_d
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2008
    Posts
    84
    Quote Originally Posted by math_science_dude View Post
    denise,

    This is a standard problem in elementary number theory. I'll provide you with my general approach but I'll leave some details up to you.

    First given the nature of what we want to prove, we infer that n is a postive integer. Let d = gcd(a,n) and e = gcd(b,n). We show that de|n and n|de (Recall a|b denotes a divides b). Now clearly since d|a and e|b, it follows that de|ab. Now as gcd(ab,n) = n (why? because ab = 0 (mod n)), we have de|n.

    To show that n|de, we use another property of gcd. Recall by Bezout's theorem that there exist integers x and y such that gcd(a,b) = ax + by. So apply this to d and e and you will see that since ab = 0 (mod n), it follows that n|de.

    I hope this is of some help to you. Feel free to give me reps (whatever that is) Good Luck!

    Best,

    m_s_d
    Thank you for your suggestions.
    Actually, I completed the second part of the proof.
    It's the first part that gave me . I will try out the proof again.
    Thanks again.
    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

Search Tags


/mathhelpforum @mathhelpforum