# if a|b and a>0 then gcd(a,b)=a

Is this proof right?

Prove: if a|b and a>0 then gcd(a,b)=a.

Let a|b and the GCD(a,b) = m, then b=aq for some integer q and the GCD(a,b) can be expressed as a linear combination with some integer x and y,

       ax + by = m .


Substituting in b we get,

      ax + (aq)y = m
a(x + qy) = m


But x + qy = GCD(1,q) =1. Thus,

      a(1) = m


Hence a = GCD(a,b), which is what we needed to show.

Thanks for all the comments :)

Update 1: I did not think I said that x and y were any integer I said that there was some integer x and some integer y so that ax +by = m Since I am supposing that the GCD(a,b) = m and a|b, then by substituting b into the GCD(a,b), then

      GCD(a,b)=GCD(a,aq)

=a*GCD(1,q) Which is a property of GCD


But the GCD(1,q)=1. So, GCD(a,b) = a

• No, there is no reason for $x+qy=1$. Just because $\gcd(1,q)=1$ doesn't mean that for all x,y, you get $x+qy=1$. So you have to answer why it is $=1$. – Thomas Andrews Sep 9 '17 at 2:49
• sadly, things do not work like that. it's "there exists $x,y$", not "for all $x,y$". – MAN-MADE Sep 9 '17 at 2:51
• Is $a,b\in\mathbb{Z}$ or just a random integer domain $R$? Why not just go by definition. It kinda follows immediatly. – Cornman Sep 9 '17 at 2:57
• I would not allow you to use GCD (a,aq)=aGCD (1,q) if you haven't proven GCD (a,b)=a if a|b first. It's circular, as both require the same observations to prove. Anyway, this is preposterous complicated for something that is essentially trivial: a divides b and a so it is a common divisor. Anything bigger than a can'can't divide a so it is the greatest common divisor. That's it. – fleablood Sep 9 '17 at 6:36

$a|b \Rightarrow b=aq$, for some integer $q$.
If $a\geq 1$, then what is the largest integer which divides both $a$ and $aq$?
$a|a$ and $a|b$ so $a$ is a common divisor of $a$ and $b$.
Anything bigger than $a$ cannot divide $a$. So $a$ is the greatest common divisor.