Extended Euclidean Algorithm

Routine Summary

Calculates the GCD of two numbers.

Inputs

A,B - Whole numbers

Outputs

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

TI-83/84/+/SE/CSE/CE

Author

kg583

:{A,B→L₁
:{1,0→L₂
:{0,1→L₃
:1→I
:While L₁(dim(L₁
:I+1→I
:int(L₁(Ans-1)/L₁(Ans→Q
:L₁(I-1)-AnsL₁(I→L₁(I+1
:L₂(I-1)-QL₂(I→L₂(I+1
:L₃(I-1)-QL₃(I→L₃(I+1
:End


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

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

.