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

• Notably, this is the converse of Bezout's identity, which gives us that, for $a,b$ coprime, then there exist $x,y$ integers such that $ax+by=1$. The converse is discussed on MSE here -- math.stackexchange.com/questions/1279900/… – Eevee Trainer Mar 26 at 3:30
• Now you need to prove that $k|k+1$ is impossible for $k>1$. If you had done the argument at the end with $ma+nb=1$ to say that $k$ would divide $1$, then would have only had to prove that $k|1$ is impossible for $k>1$. – user647486 Mar 26 at 3:32
• Shorter argument: if $k = \operatorname{gcd}(a, b)$, then $a = xk$ and $b = yk$ for integers $x$ and $y$. Thus $$1 = am + bn = k(xm + yn),$$ i.e. $k$ divides $1$. – Theo Bendit Mar 26 at 3:38

## 2 Answers

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.

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