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

1. ## 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

2. ## 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.