# Greatest common divisor theorem

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$.

• use well-ordering principle on an appropriate subset of the set $S=\{nx+my \, | \, x,y \in \mathbb{Z}\}$. – Anurag A Apr 7 '16 at 18:10
• Take the smallest positive value of $tn+ms$ for any integers (positive or negative) $t,s$. It is not hard to show that this value must be the gcd. – almagest Apr 7 '16 at 18:11
• If you want to explicitly find $t$ and $s$, then you can use the extended Euclidean algorithm. – carmichael561 Apr 7 '16 at 18:12
• Still don't know how almagest. Nice book tho, Ptolemeu? – Hemispherr Apr 7 '16 at 18:33
• – lhf Apr 7 '16 at 19:13

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}$