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

This is the shortest proof that I could think of:
Suppose $a, b \in \mathbb{N}$. Let $am + bn = 1$  for $m, n \in \mathbb{Z}$.
Now, if $am + bn = 1$ then this implies there's a solution to the congruence $am \equiv 1 \mod b$. Now, let $d= \gcd(a, b)$ where $d>0$.
Then, we have;
$$b \vert (am-1)$$ and $$d \vert b$$ and so $$ d \vert(am-1)$$
Since $d \vert a$ also, it must be that $d \vert -1$. Thus $d=1$, and, hence, $a$ and $b$ are co-prime as $gcd(a, b) = 1$.
