Prove that gcd(a,b) is the smallest positive integer that can be written as xa+yb for some x,y belong Z .?

Question

Prove that gcd(a,b) is the smallest positive integer that can be written as xa+yb for some x,y belong Z .?

Answer 1

Consider the set of positive integers

S = {z: z = ax+by; x,y ∈ Z; z > 0}

it's not difficult to see that S is always nonempty, so it must have a minimum element m = min(S).

Now, every common divisor of a and b divides m, so

gcd(a,b)|m ⇒ gcd(a,b) ≤ m

Furthermore, if m|a and m|b, then we have immediately gcd(a,b) = m.  

Suppose then that m doesn't divide a (the argument is the same for b)then, by the division theorem:

a = mq + r, 0 < r < m

Then we would have:

r = a − mq = a − (ax0 + by0)q  Ã¢Â‡Â’

⇒ r = a(1 − qx0) + b(−qy0)  

So r ∈ S, which is impossible.