Show that gcd(a,b) is the smallest positive element in the set {ma+nb}

[docnet]

Homework Statement

let $a,b\in\mathbb{N}$. Show that $gcd(a,b)$ is the smallest positive element in the set $\{ma+nb|m,n\in\mathbb{Z}\}$.

Relevant Equations

(1) If $a$ and $b$ are relatively prime, then tere are integers $m$ and $n$ such that $ma+nb=1$

(2) If $a>b$ then $gcd(a-b,b)=gcd(a,b)$

$m$, $n$, $a$, and $b$ are in $\mathbb{Z}$. The set of natural numbers is an abelian group, so $\{ma+nb|m,n\in\mathbb{Z}\}$ is a subset of $\mathbb{Z}$.

$a$ and $b$ are either relatively prime or not relatively prime.

If $a$ and $b$ are relatively prime, then there are integers $m$ and $n$ such that $ma+nb=1$. $1$ is the smallest positive element in $\mathbb{Z}$. So, $1$ is the positive smallest positive element in $\{ma+nb|m,n\in\mathbb{Z}\}$.

If $a$ and $b$ are not relatively prime, then there is an integer $c$ that commonly divides $a$ and $b$. So $a=\tilde{a}c$ and $b=\tilde{b}c$, where $\tilde{a}$ and $\tilde{b}$ are relatively prime integers.
\begin{align}ma+nb=&m\tilde{a}c+n\tilde{b}c\\
=&c(m\tilde{a}+n\tilde{b})\end{align}
$\tilde{a}$ and $\tilde{b}$ are relatively prime, so there exist integers $m$ and $n$ such that $m\tilde{a}+n\tilde{b}=1$, And because they are relatively prime, $gcd(\tilde{a},\tilde{b})=1$,
\begin{align}=& c\cdot gcd(\tilde{a},\tilde{b})=gcd(a,b)=c\end{align}
$1$ is the smallest positive element in $\{m\tilde{a}+n\tilde{b}|m,n\in\mathbb{Z}\}$ so
$c\cdot 1 =gcd(a,b)$ is the smallest positive element in $c\cdot \{m\tilde{a}+n\tilde{b}|m,n\in\mathbb{Z}\}=\{ma+nb|m,n\in\mathbb{Z}\}$.

 

[fishturtle1]

Homework Statement:: let $a,b\in\mathbb{N}$. Show that $gcd(a,b)$ is the smallest positive element in the set $\{ma+nb|m,n\in\mathbb{Z}\}$.
Relevant Equations:: (1) If $a$ and $b$ are relatively prime, then tere are integers $m$ and $n$ such that $ma+nb=1$

(2) If $a>b$ then $gcd(a-b,b)=gcd(a,b)$

The set of natural numbers is an abelian group

Under what addition?

If a and b are not relatively prime, then there is an integer c that commonly divides a and b.

Later the proof says $c = \gcd(a, b)$.

What are $m, n$ in line (1)?

so there exist integers m and n such that ma~+nb~=1,

are these the same $m, n$ as before?Hint: Let $ma + nb$ be an arbitrary positive element in $\lbrace xa + yb \vert x, y \in \mathbb{Z} \rbrace$ and define $d = \gcd(a, b)$. Then $d \vert ma + nb$. (why?).

 

[docnet]

Under what addition?

Oh no. The correct statement was "The set $\mathbb{Z}$ is closed under multiplication and addition, so the element $ma+nb$ for any $a,b,n,m\in\mathbb{Z}$ is also in $\mathbb{Z}$.

Later the proof says $c = \gcd(a, b)$.

I am confused. Is this not true when $a$ and $b$ are not co-prime?

are these the same $m, n$ as before?

No. They are different integers than before.

Hint: Let $ma + nb$ be an arbitrary positive element in $\lbrace xa + yb \vert x, y \in \mathbb{Z} \rbrace$ and define $d = \gcd(a, b)$. Then $d \vert ma + nb$. (why?).

Okay, I will try to come up with the correct solution using this hint. Thank you.