Results 1 to 4 of 4

Math Help - Greatest common divisor proof

  1. #1
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Greatest common divisor proof

    If gcd(m,n)=1 and gcd(k,n)=1, show that gcd(mk,n)=1.
    I have tried approaching it by doing a proof of the contrapositive, but I keep getting stuck..

    Let m,k,n be integers such that gcd(mk,n)\neq{1}. Then there exists d>1 such that d=gcd(mk,n). Then, d divides mk and d divides n. So, d divides (mk+n) etc....

    any advice on where to go from here?? thanks!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Greatest common divisor proof

    Quote Originally Posted by sfspitfire23 View Post
    If gcd(m,n)=1 and gcd(k,n)=1, show that gcd(mk,n)=1.
    I have tried approaching it by doing a proof of the contrapositive, but I keep getting stuck..

    Let m,k,n be integers such that gcd(mk,n)\neq{1}. Then there exists d>1 such that d=gcd(mk,n). Then, d divides mk and d divides n. So, d divides (mk+n) etc....

    any advice on where to go from here?? thanks!!!
    Can you use the fact that (m,n)=1 if and only if mx+ny=1 for some x,y\in\mathbb{Z}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,383
    Thanks
    750

    Re: Greatest common divisor proof

    if we can find integers s,t such that (mk)s + nt = 1, we'll be done.

    we know that there exist integers x,y and u,v such that: mx + ny = 1 and ku + nv = 1.

    can you see what to do next? hint: 1*1 = 1, so maybe if we multiply...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Re: Greatest common divisor proof

    Great!! Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 15th 2011, 03:00 PM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Greatest common divisor Proof (very hard!)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 26th 2009, 03:19 PM
  4. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 03:24 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2008, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum