Extended Euclidean Algorithm for Bézout Coefficients

Bézout's lemma tells us that the greatest common divisor of two integers can be written as an integer linear combination of the two integers. The question then arises as to how we can determine the two coefficients. This is where the extended Euclidean algorithm comes into play. Amazingly, it turns out that we can use the sequence of quotients and remainders from the Euclidean algorithm to produce the coefficients. This is usually expressed as an algorithm involving substitutions into equations, but we have preferred to express the idea as a neat formula involving matrix multiplication and the determinant.

Like, subscribe, and share! To find out more about us:
- Reach out on Twitter at @ExistsforallA

Copyright © Existsforall Academy Inc. All rights reserved.