# 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

### This page exists due to the efforts of the following people:

#### Timur

Created: 2014-02-23 20:21:22, Last updated: 2021-02-10 05:25:39

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/3298/. Also, please do not modify any references to the original work (if any) contained in this content.

This site already has The greatest common divisor of two integers, which uses the Euclidean algorithm. As it turns out (for me), there exists an 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 computing 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 algorithm

Greatest Common Divisor

Coefficient for bigger integer

Coefficient for smaller integer

The 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$

The start of recursion backtracking is the end of the 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.

URL copied to clipboard
PLANETCALC, Extended Euclidean algorithm