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

GCD as a linear combination

#gcd#linear combination#Bézout

Statement

Show that $\gcd(a,b)$ is the smallest positive integer of the form $au+bv$ with $u,v\in\mathbb{Z}$ .

Hint

Let $d=\gcd(a,b)$ and $m$ the smallest positive $au+bv$ . Show $m\mid a$ and $m\mid b$ , then $m\le d$ ; and $d\mid m$ , so $d\le m$ .

Show solutionHide solution

Solution

Setup. Let $m=\min\{au+bv>0:u,v\in\mathbb{Z}\}$ , achieved at $(u_0,v_0)$ .

$m\mid a$ . Euclidean division: $a=qm+r$ with $0\le r<m$ . Then $r=a-qm=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)$ is a positive combination if $r>0$ , contradicting minimality. So $r=0$ .

$m\mid b$ . Same argument.

Conclusion. $m$ is a common divisor, so $m\le d$ . Conversely, $d\mid a$ and $d\mid b$ imply $d\mid m$ , so $d\le m$ . Hence $m=d$ .

GCD as a linear combination

Statement

Solution

More problems in Divisibility and gcd