Proof if $\gcd (a, b) = 1$ then there exists $m$ and $n$ such that $am+bn=1$ Proof if $\gcd (a, b) = 1$.
Is it correct to say $\gcd (a, b) = 1$ THEN there exists coefficients $m$ and $n\in\mathbb Z$ such that $ma + nb = 1$ ? 
I assume it's right (relatively primes) but I wanted to double check...
 A: It seems that other answers address the "$\Leftarrow$" rather than "$\Rightarrow$" implication, so here is how $(a,b)=1$ implies $am+bn=1$:
If you know the Euclidean Algorithm for finding greatest common divisor, you can use it to prove the claim (and it is also useful for finding the $m$ and $n$ in practice). The Euclidean Algorithm gives you
\begin{align}
a&=b x_1+r_1\\
b&=r_1 x_2+r_2\\
&\ \ \vdots\\
r_{n-2} &= r_{n-1} x_{n}+r_n\\
r_{n-1} &= r_{n} x_{n+1}+g
\end{align}
where $g$ is the greatest common divisor, (in your case $g=1$). You can write this backwards as
\begin{align}
g&=r_{n-1}-r_n x_{n+1}\\
r_n&=r_{n-2}-r_{n-1} x_{n}\\
&\ \ \vdots\\
r_2&=b-r_1 x_2\\
r_1&=a-b x_1
\end{align}
So you are able to write $g$ as a linear combination of $r_{n-1}$ and $r_n$. Then you are also able to write $r_n$ as a linear combination of $r_{n-1}$ and $r_{n-2}$. This way you eventually reach $r_1$ which you can write as a linear combination of $a$ and $b$. Substituting this all the way gives you $g$ as a linear combination of $a$ and $b$, or $g=am+bn$ which is what you wanted.
So let's say for example $a=10$, $b=7$. By Euclidean Algorithm:
\begin{align}
10&=7\cdot 1+3\\
7&=3\cdot2+1
\end{align}
and so
$$1=7-3\cdot 2=7-(10-7\cdot 1)\cdot 2 = 3\cdot 7-2\cdot 10.$$
A: Suppose $au+bv=1$ for some integers $u,v$. Let $d:=\gcd(a,b)$ then we have $a=a'd$ and $b=b'd$ for some integers $a',b'$. Hence,
$$1=au+bv=a'du+b'dv=d(a'u+b'v)$$and thus $d\mid 1$.
A: Let $d=\gcd(a,b)$ 
Then $d|a$ and $d|b\Rightarrow$ 
$d|ma$, $d|nb$ and $d|ma+nb=1\Rightarrow d|1\Rightarrow d=1$
