how to prove m = gcd(a, b)

Question

et $a, b \in \mathbb N$, assume they are not both $0$. Define $L = \{n\in\mathbb N^+ \mid \exists x, y \in \mathbb{Z}: n = ax + by\}$

how do I prove the following claim without using gcd(a, b) = ax + by

$m = gcd(a, b)$

we know that

m = min(L)

m divides a

m divides b

Answer 1

Hint: First prove that $m\geq \gcd(a,b)$. Then prove that $\gcd(a,b)$ is attainable as a value of $ax+by$.

Answer 2

I assume that you are given that $m=\min(L) \in L$ (otherwise use well-ordering principle). This means there exists $x_0,y_0 \in \mathbb{Z}$ such that $m=ax_0+by_0$. Since you already know that $m | a$ and $m|b$, therefore $m$ is a common divisor.

Now only thing left to prove is that any common divisor $d$ of $a$ and $b$ will divide $m$.

For that let $a=dr$ and $b=ds$, then \begin{align*} m & = ax_0+by_0\\ & = d(rx_0+sy_0). \end{align*}
Thus $d | m$.

Answer 3

Hmmph.... If it were up to me I'd simply ignore everything about $m$.

I'd start by pointing out that if $n = ax + by$ then $n = \gcd(a,b) [\frac a{\gcd(a,b)}x + \frac b{\gcd(a,b)}y]$ so that $\gcd(a,b)$ will divide every element of $L$.

And $\gcd(a,b) = a*\frac {a}{\gcd(a,b)} + b*0$ so $\gcd(a,b)\in L$.

If $0< k < \gcd(a,b) $ then $\gcd(a,b) \not \mid k$ so $k \not \in L$.

So $\gcd(a,b) = \min L$.