In
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
and
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
, the extended Euclidean algorithm is an extension to the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an e ...
, and computes, in addition to the
greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
, which are integers ''x'' and ''y'' such that
:
This is a
certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.
It allows one to compute also, with almost no extra cost, the quotients of ''a'' and ''b'' by their greatest common divisor.
also refers to a
very similar algorithm for computing the
polynomial greatest common divisor
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common ...
and the coefficients of Bézout's identity of two
univariate polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
s.
The extended Euclidean algorithm is particularly useful when ''a'' and ''b'' are
coprime. With that provision, ''x'' is the
modular multiplicative inverse of ''a''
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is ...
''b'', and ''y'' is the modular multiplicative inverse of ''b'' modulo ''a''. Similarly, the polynomial extended Euclidean algorithm allows one to compute the
multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a fraction ''a''/' ...
in
algebraic field extensions and, in particular in
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s of non prime order. It follows that both extended Euclidean algorithms are widely used in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
. In particular, the computation of the
modular multiplicative inverse is an essential step in the derivation of key-pairs in the
RSA public-key encryption method.
Description
The standard Euclidean algorithm proceeds by a succession of
Euclidean divisions whose quotients are not used. Only the ''remainders'' are kept. For the extended algorithm, the successive quotients are used. More precisely, the standard Euclidean algorithm with ''a'' and ''b'' as input, consists of computing a sequence
of quotients and a sequence
of remainders such that
:
It is the main property of
Euclidean division that the inequalities on the right define uniquely
and
from
and
The computation stops when one reaches a remainder
which is zero; the greatest common divisor is then the last non zero remainder
The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows
:
The computation also stops when
and gives
*
is the greatest common divisor of the input
and
* The Bézout coefficients are
and
that is
* The quotients of ''a'' and ''b'' by their greatest common divisor are given by
and
Moreover, if ''a'' and ''b'' are both positive and
, then
:
for
where
denotes the
integral part of , that is the greatest integer not greater than .
This implies that the pair of Bézout's coefficients provided by the extended Euclidean algorithm is the ''minimal pair'' of Bézout coefficients, as being the unique pair satisfying both above inequalities .
Also it means that the algorithm can be done without
integer overflow by a
computer program
A computer program is a sequence or set of instructions in a programming language for a computer to Execution (computing), execute. Computer programs are one component of software, which also includes software documentation, documentation and oth ...
using integers of a fixed size that is larger than that of ''a'' and ''b''.
Example
The following table shows how the extended Euclidean algorithm proceeds with input and . The greatest common divisor is the last non zero entry, in the column "remainder". The computation stops at row 6, because the remainder in it is . Bézout coefficients appear in the last two entries of the second-to-last row. In fact, it is easy to verify that . Finally the last two entries and of the last row are, up to the sign, the quotients of the input and by the greatest common divisor .
Proof
As
the sequence of the
is a decreasing sequence of nonnegative integers (from ''i'' = 2 on). Thus it must stop with some
This proves that the algorithm stops eventually.
As
the greatest common divisor is the same for
and
This shows that the greatest common divisor of the input
is the same as that of
This proves that
is the greatest common divisor of ''a'' and ''b''. (Until this point, the proof is the same as that of the classical Euclidean algorithm.)
As
and
we have
for ''i'' = 0 and 1. The relation follows by induction for all
:
:
Thus
and
are Bézout coefficients.
Consider the matrix
:
The recurrence relation may be rewritten in matrix form
:
The matrix
is the identity matrix and its determinant is one. The determinant of the rightmost matrix in the preceding formula is −1. It follows that the determinant of
is
In particular, for
we have
Viewing this as a Bézout's identity, this shows that
and
are
coprime. The relation
that has been proved above and
Euclid's lemma show that
divides , that is that
for some integer . Dividing by
the relation
gives
So,
and
are coprime integers that are the quotients of and by a common factor, which is thus their greatest common divisor or its
opposite.
To prove the last assertion, assume that ''a'' and ''b'' are both positive and
. Then,
, and if