Greatest common divisor theorem

Question

Is there a way to prove that if $(n,m)=d$, then there are two integers $t$ and $s$, so that $t*n + m*s = d$? By $(n,m)$ I note the greatest common divisor of $n$ and $m$.

Answer 1

Yes it can be proven.

Proof:

Let $S=\{nx+my\, | \,x,y\in \mathbb{Z}\}$. We note that $S$ contains at least one positive integer since $n^2+m^2\geq 0$, and thus by the Well-Ordering Axiom there is a smallest positive element $d$ in $S$. Since $d\in S$ we can write $d=ns+mt$ for some $s,t \in \mathbb{Z}$.

We claim that $d=(n,m)$.

First we show that $d|n$. By the Division Algorithm $n=dq+r$ for some integers $q$ and $r$, where $0\leq r < d$. Now $$ r=n-dq \Rightarrow r=n-nsq-mtq \Rightarrow r=n(1-sq)+m(-tq)$$

Thus $r\in S$ and $r<d$. Since $d$ is the smallest positive element of $S$ this means that $r$ is not positive, i.e $r\leq 0$. Since also $r\geq 0$, we have that $r=0$. Now $n=dq$ and thus $d|n$.

Similarly we can show $d|m$.

If there is another common divisor $c$ of $m$ and $n$, then $m=cu$ and $n=cv$. Now since $d=ns+mt=cvs+cut=c(vs+ut)$ we have that $c|d$, i.e. $c\leq d$. This means that $d=(n,m)$.

$\mathit{Q.E.D}$