Proof if $\gcd (a, b) = 1$ then there exists $m$ and $n$ such that $am+bn=1$

Question

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

Answer 1

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

Answer 2

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$

Answer 3

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