1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Eevee Trainer Mar 26 at 3:30
  • $\begingroup$ 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$. $\endgroup$ – user647486 Mar 26 at 3:32
  • 1
    $\begingroup$ 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$. $\endgroup$ – Theo Bendit Mar 26 at 3:38
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.