Proof of Bézout's identity - Cohn - CA p26

Question

Given two integers $a$ and $b$, there exist integers $u$ and $v$ such that $$au+bv=1$$ if and only if $a$ and $b$ are coprime.

---

Attempt Proof:

Assume $a$ and $b$ are not coprime, e.g. $a=kb,k\in \mathbb{Z}$.

$$bku+bv=1$$ $$b(ku+v)=1$$ $$ku+v=\frac1b$$ $ku+v$ is integer, so $\frac1b$ is integer, hence $b=\pm1$ $$ku+v=\pm1$$

Case $1$: $ku+v=1$, hence $ku$ and $v$ are consecutive integers in magnitude or something.

Case $2$: $ku+v=-1$...

---

I think this is the sort of direction I need to go, but I am unsure what to do here.

Answer 1

The existence is guaranteed by the Euclidian Algorithm (as far as you have learned it already). For the converse, if $au+bv=1$ is given and $k$ is a common divisor of $a$ and $b$, then the left hand side is divisable by $k$ (because there are $l,m$ such that $a=lk$ and $b=mk$, and this implies $1=au+bv=lku+mkv=k(lu+mv)$), so $k|1$. Thus, $k=1$ and therefore $a$ and $b$ are coprime.

Answer 2

If $a>b\geqslant0$, then $a-b$ and $b$ are coprime. We get $(a-b)x+by=1$ for some $x$ and $y$ by induction, which implies $ax+b(y-x)=1$. The converse is trivial.