- #1

docnet

Gold Member

- 784

- 460

- 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}\}##.

##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}\}##.