If $d \mid a,b$ and $\exists x,y \in Z : d = ax + by$, then $d = \gcd(a,b)$

Question

If $d \mid a,b$ and $\exists x,y \in Z : d = ax + by$, then $d = \gcd(a,b)$

Well, I've tried by saying that $\gcd(a,b) \iff d = a s \cdot b t$, and now $s=x,t=y$, and I've proved it.

I've also tried to find counter examples and failed. Although my proof seems to be odd, I'm looking forward to see what you can say about this. Thanks

Answer 1

To show the statement "$d = \gcd(a,b)$", we should show (i) that $d$ divides $a$ and $b$, and (ii) that $d$ is the greatest such divisor, i.e. for any common divisor $k$ of $a$ and $b$, $k$ divides $d$.

Conveniently, (i) is given to us as a hypothesis.

For (ii), assume that $k$ divides $a$ and $b$. Now use the fact that $d = ax + by$. Can you conclude that $k$ divides $d$?