# Math Help - another gcd property

1. ## another gcd property

Let $a, b$ be integers, not both equal to zero, $d = min\{ax + by|x, y \in Z\}$. Prove $d = gcd(a, b)$

Attempt: I can do final part of proof: If $d | a$ and $d | b$, then $d | gcd(a, b)$. From $\exists x_0, y_0$, s.t. $d = ax_0 + by_0$ we have $gcd(a,b) | d$. From $gcd(a,b) | d$ and $d | gcd(a,b)$ finally $d = gcd(a,b)$.

But I can't prove that $d | a$ and $d | b$.

Can anyone help please? Thank you!

2. ## Re: another gcd property

Assume that a gives a remainder 0 < r < d when divided by d and prove that r is a linear combination of a and b smaller than d.

You need to make a restriction that some numbers are positive in this problem because d = min{ax + by | x, y in Z} does not exist.

3. ## Re: another gcd property

thanks very much! This forum is great!