Prove that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime. Suppose $a,b \in \mathbb{N}$. Prove  that if there are integers $m$ and $n$ such that $am +bn =1$ then $a$ and $b$ are coprime. 
I came up with the following proof, but I am sure a shorter argument is possible.
To prove: $\forall a,b \in \mathbb{N}$ ,  $\exists  m,n \in \mathbb{Z}$ |  $am + bn = 1\rightarrow $ $gcd(a,b) = 1$
In order to prove this by contradiciton, suppose then that $\exists m,n \in \mathbb{Z}$ |  $am + bn = 1$ and that $gcd(a,b) \neq 1$. 
Take $ k = gcd(a,b) \neq 1$. Now, $k = ra+sb$ and $s,b \in \mathbb{Z}$, assuming that k can be written as a linear combination of a and b. This is an established theorem. 
So we have:
(1) $am + bn = 1$
(2) $ra + sb = k$
Adding $(1) + (2)$ , we get :
$(r+m)a + (s+n)b = k+1$ 
Since $ k= gcd(a,b)$, then $k|(r+m)a$ and $k|(s+n)b$. Then $k|(r+m)a + (s+n)b = k+1$.  
So $k|k+1$. But this is impossible, since dividing $k \neq1$ into $k$ gives a remainder of 1. 
Having derived this contradiction, it cannot be the case that if $am + bn = 1$, then $gcd(a,b) \neq 1$. So it must be the case that:
($\exists  m,n \in \mathbb{Z}$ |  $am + bn = 1$) $\rightarrow $ ($gcd(a,b) = 1$)

Suppose $am+bn=1$. If $k$ divides both $a$ and $b$ then there exist $p$ and $q$ such that $a=kp$ and $b=kq$.
Substituting that into our first equation gives $kpm+kqn=1\implies k$ divides $1$
Therefore, $k=1$ and $a$ and $b$ are coprime. 
