Extended Euclidean Algorithm

Routine Summary

Calculates the GCD of two numbers.


A,B - Whole numbers


L₁(I) - Greatest common divisor (gcd) of A and B
L₂(I), L₃(I) - Bézout coefficients such that AL₂(I)+BL₃(I) = L₁(I)

Variables Used

I, Q

Calculator Compatibility




:While L₁(dim(L₁

The Extended Euclidean Algorithm is a highly efficient algorithm for calculating the greatest common divisor (GCD) of two numbers. The algorithm, in the process of finding the GCD, also finds the Bézout coefficients x and y. These are integers such that

\begin{align} ax+by=\gcd(a,b) \end{align}


Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 License.