Extended Euclidean Algorithm

We're glad you came by, but you might find what you're looking for elsewhere. TI-Basic Developer is not the site it once was. While its information on commands and other calculator features remains almost second-to-none, its forum, archives, and even hosting service, Wikidot, have been decaying for years. The calculator community would love to see what you're working on, or help you in your next coding adventure, but TI-Basic Developer is no longer the place to do it. Instead, you should head over to Cemetech (primarily American) or TI-Planet (primarily international). Both are active, well-established forums with their own archives, chatrooms, reference material, and abundant coding tools and resources. We'll see you there, we hope.

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}

.