Get reference code
Appearance
Sample
StudyMath

Extended Euclidean algorithm

This calculator implements Extended Euclidean algorithm, which computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout's identity
Timur2014-02-23 20:21:22

This site already has The greatest common divisor of two integers, which uses Euclidean algorithm. As it turns out (for me), there exists Extended Euclidean algorithm. This algorithm computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout's identity, that is integers x and y such that

ax + by = {\rm gcd} (a, b)

So it allows to compute the quotients of a and b by their greatest common divisor.

You can see the calculator below, and theory, as usual, us under the calculator

Extended Euclidean algorithmCreative Commons Attribution/Share-Alike License 3.0 (Unported)
 
 
 

Extended algorithm uses recursion, and computes coefficients on its backtrack. The formulas for calculations can be obtained from the following considerations:

Let us know coefficients (x_1,y_1) for pair (b\%a,a), such as:

 (b \% a)x_1 + ay_1 = g,

and we need to calculate coefficients for pair (a,b), such as:

 ax + by = g

First, we replace b\%a with:

b\%a = b - \left\lfloor \frac{b}{a} \right\rfloor a, where

\left\lfloor \frac{b}{a} \right\rfloor - quotient from integer division of b to a,

and use it as substitute in:

g = (b \% a) x_1 + a  y_1 = \left( b -\left\lfloor \frac{b}{a} \right\rfloor a\right) x_1 + ay_1

Then, after regroup we get:

g = bx_1 + a \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1\right)

By comparing this with starting equation we can express x and y:

x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor x_1
y = x_1

Start of recursion backtracking is the end of Euclidean algorithm, when a = 0 and GCD = b, so first x and y are 0 and 1 respectively. Further coefficients are computed using the formulas above.

Request a calculator
View all calculators
(467 calculators in total. )

Comments

 All discussions
Spam filter