Exercise 915Number theory › Divisibility and gcdL1Added 3 Nov 2026

Linear relations and coprimality

#coprime#linear relation#proof

Statement

Show that $a$ and $b$ are coprime iff there exist $u,v\in\mathbb{Z}$ with $au+bv=1$ .

Hint

Forward: Bézout. Converse: any common divisor divides $1$ .

Show solutionHide solution

Forward. Bézout's identity for coprime integers.

Converse. If $d\mid a$ and $d\mid b$ , then $d\mid au+bv=1$ . So $d=1$ .

Conclusion. Coprimality is equivalent to the existence of a Bézout relation equal to $1$ .