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.