1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ use well-ordering principle on an appropriate subset of the set $S=\{nx+my \, | \, x,y \in \mathbb{Z}\}$. $\endgroup$ – Anurag A Apr 7 '16 at 18:10
  • $\begingroup$ 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. $\endgroup$ – almagest Apr 7 '16 at 18:11
  • $\begingroup$ If you want to explicitly find $t$ and $s$, then you can use the extended Euclidean algorithm. $\endgroup$ – carmichael561 Apr 7 '16 at 18:12
  • $\begingroup$ Still don't know how almagest. Nice book tho, Ptolemeu? $\endgroup$ – Hemispherr Apr 7 '16 at 18:33
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Extended_Euclidean_algorithm. $\endgroup$ – lhf Apr 7 '16 at 19:13
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.