Proof verification: elementary Number Theory Proof of $am+bn = 1$ Can anyone find a hole in my proof or tell me how to make it stronger or simpler? The "lemma above" referenced in the fourth paragraph is a small but solid proof showing that $r$ is strictly less than $b$ in the division algorithm if it's written $a=bq+r$.

$\mathbf {Theorem}$ If $m$ and $n$ are positive integers that are relatively prime, then there are integers $a$ and $b$ such that $am+bn=1$.
$\mathbf {Proof}$ Let $D = \{d \in \Bbb Z : am+bn>0\}$. Then there is a least element $l$ in D. Since $m$ and $n$ are relatively prime, we need only show that $l$ divides $m$ and $n$.
Suppose $l$ does not divide $m$. Then there are integers $q$ and $r$ such that $m=ql+r$. Rewritten, we have that $r=ql-m=q(am+bn)-m=qam-m+qbn=m(qa-1)+n(qb)$.
Thus, $r \in D$. By the lemma above, $r<l$, contradicting that $l$ is the least element of $D$. We conclude then that $l$ divides $m$. Switching $m$ for $n$ gives the same result for $n$.
Since $m$ and $n$ are relatively prime, $l=1$ and it follows that there are integers $a$ and $b$ such that $am+bn=1$.

 A: proof-verification:

The "lemma above" referenced in the fourth paragraph is a small but solid proof showing that $r$ is strictly less than $b$ in the division algorithm if it's written $a=bq+r$. ("the lemma" should be clearly stated before or after the proof.)
Proof (Suppose m and n are two positive integers that are relatively prime.) Let $D = \{d \in \Bbb Z : am+bn>0\}$. (This set is ill-defined: what is the constraint for d?) Then there is a least element $l$ in D. (This is nontrivial. Can you explain?) Since $m$ and $n$ are relatively prime, we need only show that $l$ divides $m$ and $n$. (so that l must be 1, which is what we want to prove.)
Suppose $l$ does not divide $m$. Then there are integers $q$ and $r$ such that $m=ql+r$. (There should be some properties about q and r that you need later.) RewrittenRewriting it, we have that $r=ql-m=q(am+bn)-m=qam-m+qbn=m(qa-1)+n(qb)$. (Where is this rewritten formula used in the later argument?)
Thus, $r \in D$. By the lemma above ("the lemma" should be clearly stated before or after the proof.), $r<l$, contradicting that $l$ is the least element of $D$. We conclude then that $l$ divides $m$. Switching $m$ for $n$ gives the same result for $n$.
Since $m$ and $n$ are relatively prime, $l=1$ and it follows that there are integers $a$ and $b$ such that $am+bn=1$. (This sentence is redundant.)

The result you prove is called Bézout's identity. See also a proof in the linked page. 
A: suppose $\exists a,b\in Z;am+bn=1$
and we have $(m,n)=1$ (because $m$ and $n$ are positive integers that are relatively prime)
$d=(m,n)$ so $d|m$ and $d|n$
but $d|am+bn$ (according to $Theorem$:$\forall x,y\in Z; c|a \wedge  c|b \Rightarrow c|(ax+by)$
so $d|1$, but $d\in Z^*$ ($m$ and $n$ are positive integers)
so $d=1$
