Results 1 to 2 of 2

Math Help - struggling with proof: gcd(k∗a, k∗b)=k∗gcd(a, b)

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    13

    struggling with proof: gcd(k∗a, k∗b)=k∗gcd(a, b)

    For all k>0,k . Prove
    gcd(ka,kb)=kgcd(a,b)
    I think I understand what this wants but i can't figure out how to set up a formal proof. These are the guidelines we have to follow http://i.imgur.com/qpIYqPp.png

    Can anyone help me figure this out
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: struggling with proof: gcd(k∗a, k∗b)=k∗gcd(a, b)

    Any time you are working with gcd, you will probably want to start with terms of the form kax+kby. You might even want to consider the set A = \{kax+kby\in \mathbb{N} \mid x,y \in \mathbb{Z}\}. The minimum of that set is the gcd. Next show that the right hand side produces a divisor of both ka and ka. Then show it produces a greatest divisor.
    Last edited by SlipEternal; April 21st 2014 at 08:45 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Really Struggling :(
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: October 18th 2010, 08:38 AM
  2. Really struggling! Please Help.
    Posted in the Statistics Forum
    Replies: 0
    Last Post: October 1st 2010, 02:13 PM
  3. i am struggling with this, can anyone help
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: April 25th 2010, 06:28 AM
  4. Bit of help, struggling with this.
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 20th 2010, 11:47 PM
  5. I'm struggling..
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: October 21st 2008, 05:51 PM

Search Tags


/mathhelpforum @mathhelpforum