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


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

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

Thanks for the comments :)

  • 1
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Sep 9 '17 at 2:49
  • $\begingroup$ sadly, things do not work like that. it's "there exists $x,y$", not "for all $x,y$". $\endgroup$ – MAN-MADE Sep 9 '17 at 2:51
  • $\begingroup$ Is $a,b\in\mathbb{Z}$ or just a random integer domain $R$? Why not just go by definition. It kinda follows immediatly. $\endgroup$ – Cornman Sep 9 '17 at 2:57
  • $\begingroup$ 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. $\endgroup$ – fleablood Sep 9 '17 at 6:36

$a|b \Rightarrow b=aq$, for some integer $q$.

GCD means greatest common divisor.

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.

That's it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.