Maths WorkshopMaths problems with full solutions
Exercise 908Number theory › Divisibility and gcdHigh schoolAdded 3 Nov 2026

Bézout's identity

#Bézout#Euclidean algorithm#linear combination

Statement

Find integers u,vu,v such that 1071u+462v=211071u+462v=21.

Hint

Back-substitute the Euclidean algorithm from the previous exercise.

Show solutionHide solution

Solution

Back-substitution.
21=462−3⋅147,21=462-3\cdot147,
147=1071−2⋅462.147=1071-2\cdot462.
So
21=462−3(1071−2⋅462)=462−3⋅1071+6⋅462=7⋅462−3⋅1071.21=462-3(1071-2\cdot462)=462-3\cdot1071+6\cdot462=7\cdot462-3\cdot1071.

Conclusion. u=−3u=-3, v=7v=7 works: 1071⋅(−3)+462⋅7=−3213+3234=211071\cdot(-3)+462\cdot7=-3213+3234=21.

Remark. Bézout's identity exists iff gcd⁡(a,b)\gcd(a,b) divides the target; the coefficients are not unique (adding multiples of b/gcd⁡b/\gcd to uu and subtracting multiples of a/gcd⁡a/\gcd from vv gives other solutions).