Exercise 453Number theory › Divisibility and gcdHigh schoolAdded 3 Nov 2026

Coprime integers

#coprime#gcd#Bézout

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 $au+bv$ .

Show solutionHide solution

Forward. If $\gcd(a,b)=1$ , Bézout gives $u,v$ with $au+bv=1$ .

Converse. If $au+bv=1$ and $d\mid a$ , $d\mid b$ , then $d\mid au+bv=1$ , so $d=1$ . Hence $\gcd(a,b)=1$ .

Conclusion. $\gcd(a,b)=1$ iff $a$ and $b$ have a Bézout relation equal to $1$ .