Extended Euclidean Algorithm

Routine Summary

Calculates the mode(s) of a list of 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₁(I-1)/L₁(I→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 whole numbers such that

(1)
\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.