Exercise 908Number theory › Divisibility and gcdHigh schoolAdded 3 Nov 2026
Bézout's identity
#Bézout#Euclidean algorithm#linear combination
Statement
Find integers such that .
Hint
Back-substitute the Euclidean algorithm from the previous exercise.
Show solutionHide solution
Solution
Back-substitution.
So
Conclusion. , works: .
Remark. Bézout's identity exists iff divides the target; the coefficients are not unique (adding multiples of to and subtracting multiples of from gives other solutions).