Extended Euclidean Algorithm

Share calculation and page on

This calculator applies the Euclidean algorithm to calculate GCD. It also calculate Bezout coefficients by applying the extended Euclidean algorithm.

Identity of Bezout

The identity of Bezout (or Bezout's theorem or Bezout's lemma) is defined as follows:

N and P are two non-zero integers with d as their GCD (Greatest Common Divisor,

`GCD (N, P) = d`

So there exist two integers u and v such as,

`n*u + p*v = d`

Examples of Bezout coefficients

Example 1 : N = 65 and P = 39, then u = -1 and v = 2 indeed,

`65* (-1) + 39 * 2 = GCD (65.39) = 13`

Example 2 : N = 195 and P = 154, then u = -15 and v = 19 because,

`195* (-15) + 154 * 19 = GCD (195,154) = 1`

How to find Bezout coefficients ?

Bezout coefficients are calculated by applying the extended Euclidean algorithm. This method consists on applying the Euclidean algorithm to find the GCD and then rewrite the equations by "starting from the bottom". We reconsider example 2 above:

N = 195 and P = 154. The GCD is calculated according to the Euclidean algorithm:

`195 = (1) 154 + 41`
`154 = (3) 41 + 31`
`41 = (1) 31 + 10`
`31 = (3) 10 + 1`
`10 = (1) 10 + 0`

GCD (195, 154) = 1 (last non-zero remainder)

We rewrite the equations (except the last with zero remainder) as such,

`41 = 195 - (1) 154`
`31 = 154 - (3) 41`
`10 = 41 - (1) 31`
`1 = 31 - (3) 10`

We begin from the last equation and replace the quotients using the "above" division and so on:
We replace 10,
`1 = 31 - (3) (41 - (1) 31) = (4) 31 - (3) 41`

We replace 31,
`1 = (4) (154 - (3) 41) - (3) 41 = (4) 154 - (15) 41`

We replace 41,
`1 = (4) 154 - (15) (195 - (1) 154) = (19) 154 - (15) 195`

We get the same result as above,

u = -15 and v = 19

Some consequences of Bezout identity (advanced)

- N and P are two non-zero integers and d their GCD, then the multiples of d can be written N.x + P.y (x and y are integers)

- If N and P are coprime numbers then there exist two integers u and v such as N.u + p.V = 1

- A consequence of the latter property is the following :
N and P are two coprime integers then, there exists v an integer such that,
`P.v\equiv 1\mod N` (v is the modular multiplicative inverse of P modulo N)
In other words, if N and P are coprime numbers then the modular multiplicative inverse of P modulo N exists.
In fact, if N and P are coprime numbers if and only if the modular multiplicative inverse of P modulo N exists.

Programming

Python

This python program calculates the coefficients of Bezout identity (extended Euclidean algorithm).

The function bezout (a, b) returns a triplet (u, v, gcd (a, b)), u and v being the Bezout coefficients such :
`a* u + b * v = gcd (a, b) `

This function uses recursivity code (bezout (b, r)).


def bezout(a, b):
	if b == 0:
 		return 1, 0, a
 	else:
 		q = a//b
 		r = a%b
 		x, y, g = bezout (b, r)
 		return y, x - q*y, g