![Euclid's algorithm Book VII Proposition 2 3](https://upload.wikimedia.org/wikipedia/commons/3/37/Euclid%27s_algorithm_Book_VII_Proposition_2_3.png)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Euclidean algorithm,
[Some widely used textbooks, such as ]I. N. Herstein
Israel Nathan Herstein (March 28, 1923 – February 9, 1988) was a mathematician, appointed as professor at the University of Chicago in 1951. He worked on a variety of areas of algebra, including ring theory, with over 100 research papers and ov ...
's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
or Euclid's algorithm, is an efficient method for computing the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
(GCD) of two integers (numbers), the largest number that divides them both without a
remainder
In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient (integer division). In algebr ...
. It is named after the ancient Greek
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Euclid
Euclid (; grc-gre, Wikt:Εὐκλείδης, Εὐκλείδης; BC) was an ancient Greek mathematician active as a geometer and logician. Considered the "father of geometry", he is chiefly known for the ''Euclid's Elements, Elements'' trea ...
, who first described it in
his ''Elements'' (c. 300 BC).
It is an example of an ''
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
'', a step-by-step procedure for performing a calculation according to well-defined rules,
and is one of the oldest algorithms in common use. It can be used to reduce
fraction
A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
s to their
simplest form, and is a part of many other number-theoretic and cryptographic calculations.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By
reversing the steps or using the
extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
, the GCD can be expressed as a
linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
(for example, 21 = 5 × 105 + (−2) × 252). The fact that the GCD can always be expressed in this way is known as
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 ...
.
The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by
Gabriel Lamé
Gabriel Lamé (22 July 1795 – 1 May 1870) was a French mathematician who contributed to the theory of partial differential equations by the use of curvilinear coordinates, and the mathematical theory of elasticity (for which linear elasticity ...
in 1844, and marks the beginning of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
. Additional methods for improving the algorithm's efficiency were developed in the 20th century.
The Euclidean algorithm has many theoretical and practical applications. It is used for reducing
fraction
A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
s to their
simplest form and for performing
division
Division or divider may refer to:
Mathematics
*Division (mathematics), the inverse of multiplication
*Division algorithm, a method for computing the result of mathematical division
Military
*Division (military), a formation typically consisting ...
in
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
. Computations using this algorithm form part of the
cryptographic protocol
A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describe ...
s that are used to secure
internet
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
communications, and in methods for breaking these cryptosystems by
factoring large composite numbers. The Euclidean algorithm may be used to solve
Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
s, such as finding numbers that satisfy multiple congruences according to the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, to construct
continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
s, and to find accurate
rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
such as
Lagrange's four-square theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.
p = a_0^2 + a_1^2 + a_2^2 + a_ ...
and the
uniqueness of prime factorizations.
The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as
Gaussian integer
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
s and
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 exa ...
s of one variable. This led to modern
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
ic notions such as
Euclidean domains.
Background: greatest common divisor
The Euclidean algorithm calculates the greatest common divisor (GCD) of two
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s ''a'' and ''b''. The greatest common divisor ''g'' is the largest natural number that divides both ''a'' and ''b'' without leaving a remainder. Synonyms for GCD include ''greatest common factor'' (GCF), ''highest common factor'' (HCF), ''highest common divisor'' (HCD), and ''greatest common measure'' (GCM). The greatest common divisor is often written as gcd(''a'', ''b'') or, more simply, as (''a'', ''b''), although the latter notation is ambiguous, also used for concepts such as an
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
in the
ring of integers
In mathematics, the ring of integers of an algebraic number field K is the ring of all algebraic integers contained in K. An algebraic integer is a root of a monic polynomial with integer coefficients: x^n+c_x^+\cdots+c_0. This ring is often deno ...
, which is closely related to GCD.
If gcd(''a'', ''b'') = 1, then ''a'' and ''b'' are said to be
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
(or relatively prime). This property does not imply that ''a'' or ''b'' are themselves
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s. For example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1.
![24x60](https://upload.wikimedia.org/wikipedia/commons/7/74/24x60.svg)
Let ''g'' = gcd(''a'', ''b''). Since ''a'' and ''b'' are both multiples of ''g'', they can be written ''a'' = ''mg'' and ''b'' = ''ng'', and there is no larger number ''G'' > ''g'' for which this is true. The natural numbers ''m'' and ''n'' must be coprime, since any common factor could be factored out of ''m'' and ''n'' to make ''g'' greater. Thus, any other number ''c'' that divides both ''a'' and ''b'' must also divide ''g''. The greatest common divisor ''g'' of ''a'' and ''b'' is the unique (positive) common divisor of ''a'' and ''b'' that is divisible by any other common divisor ''c''.
The greatest common divisor can be visualized as follows. Consider a rectangular area ''a'' by ''b'', and any common divisor ''c'' that divides both ''a'' and ''b'' exactly. The sides of the rectangle can be divided into segments of length ''c'', which divides the rectangle into a grid of squares of side length ''c''. The GCD ''g'' is the largest value of ''c'' for which this is possible. For illustration, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the GCD of 24 and 60. A 24-by-60 rectangular area can be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).
The greatest common divisor of two numbers ''a'' and ''b'' is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as divides both ''a'' and ''b''.
For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the GCD of 1386 and 3213 equals 63 = 3 × 3 × 7, the product of their shared prime factors (with 3 repeated since 3 × 3 divides both). If two numbers have no common prime factors, their GCD is 1 (obtained here as an instance of the
empty product
In mathematics, an empty product, or nullary product or vacuous product, is the result of multiplying no factors. It is by convention equal to the multiplicative identity (assuming there is an identity for the multiplication operation in question ...
), in other words they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.
Factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
of large integers is believed to be a computationally very difficult problem, and the security of many widely used
cryptographic protocol
A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describe ...
s is based upon its infeasibility.
Another definition of the GCD is helpful in advanced mathematics, particularly
ring theory
In algebra, ring theory is the study of rings— algebraic structures in which addition and multiplication are defined and have similar properties to those operations defined for the integers. Ring theory studies the structure of rings, their re ...
.
The greatest common divisor ''g'' of two nonzero numbers ''a'' and ''b'' is also their smallest positive integral linear combination, that is, the smallest positive number of the form ''ua'' + ''vb'' where ''u'' and ''v'' are integers. The set of all integral linear combinations of ''a'' and ''b'' is actually the same as the set of all multiples of ''g'' (''mg'', where ''m'' is an integer). In modern mathematical language, the
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
generated by ''a'' and ''b'' is the ideal generated by ''g'' alone (an ideal generated by a single element is called a
principal ideal
In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
, and all ideals of the integers are principal ideals). Some properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of ''a'' and ''b'' also divides the GCD (it divides both terms of ''ua'' + ''vb''). The equivalence of this GCD definition with the other definitions is described below.
The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example,
:
Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.
Description
Procedure
The Euclidean algorithm proceeds in a series of steps, with the output of each step used as the input for the next. Track the steps using an integer counter ''k'', so the initial step corresponds to ''k'' = 0, the next step to ''k'' = 1, and so on.
Each step begins with two nonnegative remainders ''r''
''k''−2 and ''r''
''k''−1, with ''r''
''k''−2 > ''r''
''k''−1. The ''k''th step performs
division-with-remainder to find the quotient ''q''
''k'' and remainder ''r''
''k'' so that:
:
That is, multiples of the smaller number ''r''
''k''−1 are subtracted from the larger number ''r''
''k''−2 until the remainder ''r''
''k'' is smaller than ''r''
''k''−1. Then the algorithm proceeds to the (''k''+1)th step starting with ''r''
''k''−1 and ''r''
''k''''.''
In the initial step ''k'' = 0, the remainders are set to ''r''
−2 = ''a'' and ''r''
−1 = ''b'', the numbers for which the GCD is sought. In the next step ''k'' = 1, the remainders are ''r
−1 = b'' and the remainder ''r''
0 of the initial step, and so on. The algorithm proceeds in a sequence of equations
:
The algorithm need not be modified if ''a'' < ''b'': in that case, the initial quotient is ''q''
0 = 0, the first remainder is ''r''
0 = ''a'', and henceforth ''r''
''k''−2 > ''r''
''k''−1 for all ''k'' ≥ 1.
Since the remainders are non-negative integers that decrease with every step, the sequence
cannot be infinite, so the algorithm must eventually fail to produce the next step; but the division algorithm can always proceed to the (''N''+1)th step provided ''r''
''N'' > 0. Thus the algorithm must eventually produce a zero remainder ''r''
''N'' = 0. The final nonzero remainder is the greatest common divisor of ''a'' and ''b'':
Proof of validity
The validity of the Euclidean algorithm can be proven by a two-step argument. In the first step, the final nonzero remainder ''r''
''N''−1 is shown to divide both ''a'' and ''b''. Since it is a common divisor, it must be less than or equal to the greatest common divisor ''g''. In the second step, it is shown that any common divisor of ''a'' and ''b'', including ''g'', must divide ''r''
''N''−1; therefore, ''g'' must be less than or equal to ''r''
''N''−1. These two opposite inequalities imply ''r''
''N''−1 = ''g''.
To demonstrate that ''r''
''N''−1 divides both ''a'' and ''b'' (the first step), ''r''
''N''−1 divides its predecessor ''r''
''N''−2
:
since the final remainder ''r''
''N'' is zero. ''r''
''N''−1 also divides its next predecessor ''r''
''N''−3
:
because it divides both terms on the right-hand side of the equation. Iterating the same argument, ''r''
''N''−1 divides all the preceding remainders, including ''a'' and ''b''. None of the preceding remainders ''r''
''N''−2, ''r''
''N''−3, etc. divide ''a'' and ''b'', since they leave a remainder. Since ''r''
''N''−1 is a common divisor of ''a'' and ''b'', ''r''
''N''−1 ≤ ''g''.
In the second step, any natural number ''c'' that divides both ''a'' and ''b'' (in other words, any common divisor of ''a'' and ''b'') divides the remainders ''r''
''k''. By definition, ''a'' and ''b'' can be written as multiples of ''c'' : ''a'' = ''mc'' and ''b'' = ''nc'', where ''m'' and ''n'' are natural numbers. Therefore, ''c'' divides the initial remainder ''r''
0, since ''r''
0 = ''a'' − ''q''
0''b'' = ''mc'' − ''q''
0''nc'' = (''m'' − ''q''
0''n'')''c''. An analogous argument shows that ''c'' also divides the subsequent remainders ''r''
1, ''r''
2, etc. Therefore, the greatest common divisor ''g'' must divide ''r''
''N''−1, which implies that ''g'' ≤ ''r''
''N''−1. Since the first part of the argument showed the reverse (''r''
''N''−1 ≤ ''g''), it follows that ''g'' = ''r''
''N''−1. Thus, ''g'' is the greatest common divisor of all the succeeding pairs:
:
Worked example
![Euclidean algorithm 1071 462](https://upload.wikimedia.org/wikipedia/commons/1/1c/Euclidean_algorithm_1071_462.gif)
For illustration, the Euclidean algorithm can be used to find the greatest common divisor of ''a'' = 1071 and ''b'' = 462. To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (''q''
0 = 2), leaving a remainder of 147:
:
Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (''q''
1 = 3), leaving a remainder of 21:
:
Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (''q''
2 = 7), leaving no remainder:
:
Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462. This agrees with the gcd(1071, 462) found by prime factorization
above. In tabular form, the steps are:
Visualization
The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor.
Assume that we wish to cover an ''a''-by-''b'' rectangle with square tiles exactly, where ''a'' is the larger of the two numbers. We first attempt to tile the rectangle using ''b''-by-''b'' square tiles; however, this leaves an ''r''
0-by-''b'' residual rectangle untiled, where ''r''
0 < ''b''. We then attempt to tile the residual rectangle with ''r''
0-by-''r''
0 square tiles. This leaves a second residual rectangle ''r''
1-by-''r''
0, which we attempt to tile using ''r''
1-by-''r''
1 square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is 21-by-21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).
Euclidean division
At every step ''k'', the Euclidean algorithm computes a quotient ''q''
''k'' and remainder ''r''
''k'' from two numbers ''r''
''k''−1 and ''r''
''k''−2
:
where the ''r''
''k'' is non-negative and is strictly less than the
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
of ''r''
''k''−1. The theorem which underlies the definition of the
Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than ...
ensures that such a quotient and remainder always exist and are unique.
In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, ''r''
''k''−1 is subtracted from ''r''
''k''−2 repeatedly until the remainder ''r''
''k'' is smaller than ''r''
''k''−1. After that ''r''
''k'' and ''r''
''k''−1 are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the
modulo operation
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 th ...
, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply
:
Implementations
Implementations of the algorithm may be expressed in
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
. For example, the division-based version may be
programmed as
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
At the beginning of the ''k''th iteration, the variable ''b'' holds the latest remainder ''r''
''k''−1, whereas the variable ''a'' holds its predecessor, ''r''
''k''−2. The step ''b'' := ''a'' mod ''b'' is equivalent to the above recursion formula ''r''
''k'' ≡ ''r''
''k''−2 mod ''r''
''k''−1. The
temporary variable
In computer programming, a temporary variable is a variable with short lifetime, usually to hold data that will soon be discarded, or before it can be placed at a more permanent memory location. Because it is short-lived, it is usually declared ...
''t'' holds the value of ''r''
''k''−1 while the next remainder ''r''
''k'' is being calculated. At the end of the loop iteration, the variable ''b'' holds the remainder ''r''
''k'', whereas the variable ''a'' holds its predecessor, ''r''
''k''−1.
(If negative inputs are allowed, or if the mod function may return negative values, the last line must be changed into return max(a, −a).)
In the subtraction-based version, which was Euclid's original version, the remainder calculation (
b := a mod b
) is replaced by repeated subtraction. Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when ''a'' = ''b'':
function gcd(a, b)
while a ≠ b
if a > b
a := a − b
else
b := b − a
return a
The variables ''a'' and ''b'' alternate holding the previous remainders ''r''
''k''−1 and ''r''
''k''−2. Assume that ''a'' is larger than ''b'' at the beginning of an iteration; then ''a'' equals ''r''
''k''−2, since ''r''
''k''−2 > ''r''
''k''−1. During the loop iteration, ''a'' is reduced by multiples of the previous remainder ''b'' until ''a'' is smaller than ''b''. Then ''a'' is the next remainder ''r''
''k''. Then ''b'' is reduced by multiples of ''a'' until it is again smaller than ''a'', giving the next remainder ''r''
''k''+1, and so on.
The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(''r''
''N''−1, 0) = ''r''
''N''−1.
function gcd(a, b)
if b = 0
return a
else
return gcd(b, a mod b)
(As above, if negative inputs are allowed, or if the mod function may return negative values, the instruction "return a" must be changed into "return max(a, −a)".)
For illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147). The latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.
Method of least absolute remainders
In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder.
Previously, the equation
:
assumed that . However, an alternative negative remainder can be computed:
:
if or
:
if .
If is replaced by when , then one gets a variant of Euclidean algorithm such that
:
at each step.
Leopold Kronecker
Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, ...
has shown that this version requires the fewest steps of any version of Euclid's algorithm.
More generally, it has been proven that, for every input numbers ''a'' and ''b'', the number of steps is minimal if and only if is chosen in order that
where
is the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
.
Historical development
![Euklid](https://upload.wikimedia.org/wikipedia/commons/9/9e/Euklid.jpg)
The Euclidean algorithm is one of the oldest algorithms in common use.
[, p. 318] It appears in
Euclid's ''Elements'' (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths ''a'' and ''b'' corresponds to the greatest length ''g'' that measures ''a'' and ''b'' evenly; in other words, the lengths ''a'' and ''b'' are both integer multiples of the length ''g''.
The algorithm was probably not discovered by
Euclid
Euclid (; grc-gre, Wikt:Εὐκλείδης, Εὐκλείδης; BC) was an ancient Greek mathematician active as a geometer and logician. Considered the "father of geometry", he is chiefly known for the ''Euclid's Elements, Elements'' trea ...
, who compiled results from earlier mathematicians in his ''Elements''.
The mathematician and historian
B. L. van der Waerden
Bartel Leendert van der Waerden (; 2 February 1903 – 12 January 1996) was a Dutch mathematician and historian of mathematics.
Biography
Education and early career
Van der Waerden learned advanced mathematics at the University of Amsterd ...
suggests that Book VII derives from a textbook on
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
written by mathematicians in the school of
Pythagoras
Pythagoras of Samos ( grc, Πυθαγόρας ὁ Σάμιος, Pythagóras ho Sámios, Pythagoras the Samos, Samian, or simply ; in Ionian Greek; ) was an ancient Ionians, Ionian Ancient Greek philosophy, Greek philosopher and the eponymou ...
.
The algorithm was probably known by
Eudoxus of Cnidus
Eudoxus of Cnidus (; grc, Εὔδοξος ὁ Κνίδιος, ''Eúdoxos ho Knídios''; ) was an ancient Greek astronomer, mathematician, scholar, and student of Archytas and Plato. All of his original works are lost, though some fragments are ...
(about 375 BC).
The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (''anthyphairesis'', reciprocal subtraction) in works by Euclid and
Aristotle
Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of phil ...
.
Centuries later, Euclid's algorithm was discovered independently both in India and in China,
primarily to solve
Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
s that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer
Aryabhata
Aryabhata (ISO: ) or Aryabhata I (476–550 CE) was an Indian mathematician and astronomer of the classical age of Indian mathematics and Indian astronomy. He flourished in the Gupta Era and produced works such as the ''Aryabhatiya'' (which ...
described the algorithm as the "pulverizer",
perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
had already been described in the Chinese book ''
Sunzi Suanjing
''Sunzi Suanjing'' () was a mathematical treatise written during 3rd to 5th centuries AD which was listed as one of the Ten Computational Canons during the Tang dynasty. The specific identity of its author Sunzi (lit. "Master Sun") is still ...
'', the general solution was published by
Qin Jiushao
Qin Jiushao (, ca. 1202–1261), courtesy name Daogu (道古), was a Chinese mathematician, meteorologist, inventor, politician, and writer. He is credited for discovering Horner's method as well as inventing Tianchi basins, a type of rain gau ...
in his 1247 book ''Shushu Jiuzhang'' (數書九章 ''
Mathematical Treatise in Nine Sections
The ''Mathematical Treatise in Nine Sections'' () is a mathematical text written by Chinese Southern Song dynasty mathematician Qin Jiushao in the year 1247. The mathematical text has a wide range of topics and is taken from all aspects of th ...
''). The Euclidean algorithm was first described ''numerically'' and popularized in Europe in the second edition of
Bachet's ''Problèmes plaisants et délectables'' (''Pleasant and enjoyable problems'', 1624).
In Europe, it was likewise used to solve Diophantine equations and in developing
continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
s. The
extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
was published by the English mathematician
Nicholas Saunderson
Nicholas Saunderson (20 January 1682 – 19 April 1739) was a blind English scientist and mathematician. According to one historian of statistics, he may have been the earliest discoverer of Bayes' theorem. He worked as Lucasian Professor o ...
, who attributed it to
Roger Cotes
Roger Cotes (10 July 1682 – 5 June 1716) was an English mathematician, known for working closely with Isaac Newton by proofreading the second edition of his famous book, the '' Principia'', before publication. He also invented the quadratur ...
as a method for computing continued fractions efficiently.
In the 19th century, the Euclidean algorithm led to the development of new number systems, such as
Gaussian integer
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
s and
Eisenstein integers. In 1815,
Carl Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
used the Euclidean algorithm to demonstrate unique factorization of
Gaussian integer
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
s, although his work was first published in 1832.
Gauss mentioned the algorithm in his ''
Disquisitiones Arithmeticae
The (Latin for "Arithmetical Investigations") is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24. It is notable for having had a revolutionary impact on th ...
'' (published 1801), but only as a method for
continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
s.
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory. Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Lejeune Dirichlet's lectures on number theory were edited and extended by
Richard Dedekind
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
, who used Euclid's algorithm to study
algebraic integer
In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial (a polynomial whose leading coefficient is 1) whose coefficients ...
s, a new general type of number. For example, Dedekind was the first to prove
Fermat's two-square theorem using the unique factorization of Gaussian integers. Dedekind also defined the concept of a
Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described
below). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of
ideals.
Other applications of Euclid's algorithm were developed in the 19th century. In 1829,
Charles Sturm showed that the algorithm was useful in the
Sturm chain method for counting the real roots of polynomials in any given interval.
The Euclidean algorithm was the first
integer relation algorithm An integer relation between a set of real numbers ''x''1, ''x''2, ..., ''x'n'' is a set of integers ''a''1, ''a''2, ..., ''a'n'', not all 0, such that
:a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,
An integer relation algorithm is an algorithm fo ...
, which is a method for finding integer relations between commensurate real numbers. Several novel
integer relation algorithm An integer relation between a set of real numbers ''x''1, ''x''2, ..., ''x'n'' is a set of integers ''a''1, ''a''2, ..., ''a'n'', not all 0, such that
:a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,
An integer relation algorithm is an algorithm fo ...
s have been developed, such as the algorithm of
Helaman Ferguson
Helaman Rolfe Pratt Ferguson (born 1940 in Salt Lake City, Utah) is an American sculptor and a digital artist, specifically an algorist. He is also well known for his development of the PSLQ algorithm, an integer relation detection algorithm.
Ea ...
and R.W. Forcade (1979) and the
LLL algorithm LLL may refer to:
Businesses and organisations
*L3 Technologies, an American defense contractor formerly with the NYSE stock symbol LLL
*La Leche League, an organization that promotes breastfeeding
Education
* LL.L (''Legum Licentiatus''), a ...
.
In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called ''The Game of Euclid'', which has an optimal strategy. The players begin with two piles of ''a'' and ''b'' stones. The players take turns removing ''m'' multiples of the smaller pile from the larger. Thus, if the two piles consist of ''x'' and ''y'' stones, where ''x'' is larger than ''y'', the next player can reduce the larger pile from ''x'' stones to ''x'' − ''my'' stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.
Mathematical applications
Bézout's identity
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 ...
states that the greatest common divisor ''g'' of two integers ''a'' and ''b'' can be represented as a linear sum of the original two numbers ''a'' and ''b''. In other words, it is always possible to find integers ''s'' and ''t'' such that ''g'' = ''sa'' + ''tb''.
The integers ''s'' and ''t'' can be calculated from the quotients ''q''
0, ''q''
1, etc. by reversing the order of equations in Euclid's algorithm. Beginning with the next-to-last equation, ''g'' can be expressed in terms of the quotient ''q''
''N''−1 and the two preceding remainders, ''r''
''N''−2 and ''r''
''N''−3:
:
Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,
: and
:
Substituting these formulae for ''r''
''N''−2 and ''r''
''N''−3 into the first equation yields ''g'' as a linear sum of the remainders ''r''
''N''−4 and ''r''
''N''−5. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers ''a'' and ''b'' are reached:
:
:
:
After all the remainders ''r''
0, ''r''
1, etc. have been substituted, the final equation expresses ''g'' as a linear sum of ''a'' and ''b'', so that ''g'' = ''sa'' + ''tb''.
The Euclidean algorithm, and thus Bezout's identity, can be generalized to the context of
Euclidean domains.
Principal ideals and related problems
Bézout's identity provides yet another definition of the greatest common divisor ''g'' of two numbers ''a'' and ''b''.
Consider the set of all numbers ''ua'' + ''vb'', where ''u'' and ''v'' are any two integers. Since ''a'' and ''b'' are both divisible by ''g'', every number in the set is divisible by ''g''. In other words, every number of the set is an integer multiple of ''g''. This is true for every common divisor of ''a'' and ''b''. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing ''u'' = ''s'' and ''v'' = ''t'' gives ''g''. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by ''g''. Conversely, any multiple ''m'' of ''g'' can be obtained by choosing ''u'' = ''ms'' and ''v'' = ''mt'', where ''s'' and ''t'' are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by ''m'',
:
Therefore, the set of all numbers ''ua'' + ''vb'' is equivalent to the set of multiples ''m'' of ''g''. In other words, the set of all possible sums of integer multiples of two numbers (''a'' and ''b'') is equivalent to the set of multiples of gcd(''a'', ''b''). The GCD is said to be the generator of the
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considere ...
of ''a'' and ''b''. This GCD definition led to the modern
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
ic concepts of a
principal ideal
In mathematics, specifically ring theory, a principal ideal is an ideal I in a ring R that is generated by a single element a of R through multiplication by every element of R. The term also has another, similar meaning in order theory, where ...
(an ideal generated by a single element) and a
principal ideal domain
In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are principal, ...
(a
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
in which every ideal is a principal ideal).
Certain problems can be solved using this result. For example, consider two measuring cups of volume ''a'' and ''b''. By adding/subtracting ''u'' multiples of the first cup and ''v'' multiples of the second cup, any volume ''ua'' + ''vb'' can be measured out. These volumes are all multiples of ''g'' = gcd(''a'', ''b'').
Extended Euclidean algorithm
The integers ''s'' and ''t'' of Bézout's identity can be computed efficiently using the
extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
. This extension adds two recursive equations to Euclid's algorithm
:
:
with the starting values
:
:
Using this recursion, Bézout's integers ''s'' and ''t'' are given by ''s'' = ''s''
''N'' and ''t'' = ''t''
''N'', where ''N+1'' is the step on which the algorithm terminates with ''r''
''N+1'' = 0.
The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step ''k'' − 1 of the algorithm; in other words, assume that
:
for all ''j'' less than ''k''. The ''k''th step of the algorithm gives the equation
:
Since the recursion formula has been assumed to be correct for ''r''
''k''−2 and ''r''
''k''−1, they may be expressed in terms of the corresponding ''s'' and ''t'' variables
:
Rearranging this equation yields the recursion formula for step ''k'', as required
:
Matrix method
The integers ''s'' and ''t'' can also be found using an equivalent
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
method.
The sequence of equations of Euclid's algorithm
:
can be written as a product of 2-by-2 quotient matrices multiplying a two-dimensional remainder vector
:
Let M represent the product of all the quotient matrices
:
This simplifies the Euclidean algorithm to the form
:
To express ''g'' as a linear sum of ''a'' and ''b'', both sides of this equation can be multiplied by the
inverse of the matrix M.
The
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of M equals (−1)
''N''+1, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of M is never zero, the vector of the final remainders can be solved using the inverse of M
:
Since the top equation gives
:
the two integers of Bézout's identity are ''s'' = (−1)
''N''+1''m''
22 and ''t'' = (−1)
''N''''m''
12. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.
Euclid's lemma and unique factorization
Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the
unique factorization
In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is a ...
of numbers into prime factors. To illustrate this, suppose that a number ''L'' can be written as a product of two factors ''u'' and ''v'', that is, ''L'' = ''uv''. If another number ''w'' also divides ''L'' but is coprime with ''u'', then ''w'' must divide ''v'', by the following argument: If the greatest common divisor of ''u'' and ''w'' is 1, then integers ''s'' and ''t'' can be found such that
:
by Bézout's identity. Multiplying both sides by ''v'' gives the relation
:
Since ''w'' divides both terms on the right-hand side, it must also divide the left-hand side, ''v''. This result is known as
Euclid's lemma
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as w ...
.
Specifically, if a prime number divides ''L'', then it must divide at least one factor of ''L''. Conversely, if a number ''w'' is coprime to each of a series of numbers ''a''
1, ''a''
2, ..., ''a''
''n'', then ''w'' is also coprime to their product, ''a''
1 × ''a''
2 × ... × ''a''
''n''.
Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers. To see this, assume the contrary, that there are two independent factorizations of ''L'' into ''m'' and ''n'' prime factors, respectively
:
Since each prime ''p'' divides ''L'' by assumption, it must also divide one of the ''q'' factors; since each ''q'' is prime as well, it must be that ''p'' = ''q''. Iteratively dividing by the ''p'' factors shows that each ''p'' has an equal counterpart ''q''; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.
Linear Diophantine equations
Diophantine equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
s are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician
Diophantus
Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandrian mathematician, who was the aut ...
. A typical ''linear'' Diophantine equation seeks integers ''x'' and ''y'' such that
:
where ''a'', ''b'' and ''c'' are given integers. This can be written as an equation for ''x'' in
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
:
:
Let ''g'' be the greatest common divisor of ''a'' and ''b''. Both terms in ''ax'' + ''by'' are divisible by ''g''; therefore, ''c'' must also be divisible by ''g'', or the equation has no solutions. By dividing both sides by ''c''/''g'', the equation can be reduced to Bezout's identity
:
where ''s'' and ''t'' can be found by the
extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
. This provides one solution to the Diophantine equation, ''x''
1 = ''s'' (''c''/''g'') and ''y''
1 = ''t'' (''c''/''g'').
In general, a linear Diophantine equation has no solutions, or an infinite number of solutions. To find the latter, consider two solutions, (''x''
1, ''y''
1) and (''x''
2, ''y''
2), where
:
or equivalently
:
Therefore, the smallest difference between two ''x'' solutions is ''b''/''g'', whereas the smallest difference between two ''y'' solutions is ''a''/''g''. Thus, the solutions may be expressed as
:
: .
By allowing ''u'' to vary over all possible integers, an infinite family of solutions can be generated from a single solution (''x''
1, ''y''
1). If the solutions are required to be ''positive'' integers (''x'' > 0, ''y'' > 0), only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions; this is impossible for a
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three ...
when the solutions can be any
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
(see
Underdetermined system
In mathematics, a system of linear equations or a system of polynomial equations is considered underdetermined if there are fewer equations than unknowns (in contrast to an overdetermined system, where there are more equations than unknowns). The ...
).
Multiplicative inverses and the RSA algorithm
A
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 ...
is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as
commutativity
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
,
associativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
and
distributivity
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmeti ...
. An example of a finite field is the set of 13 numbers using
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced
modulo 13; that is, multiples of 13 are added or subtracted until the result is brought within the range 0–12. For example, the result of 5 × 7 = 35 mod 13 = 9. Such finite fields can be defined for any prime ''p''; using more sophisticated definitions, they can also be defined for any power ''m'' of a prime ''p''
''m''. Finite fields are often called
Galois fields, and are abbreviated as GF(''p'') or GF(''p''
''m'').
In such a field with ''m'' numbers, every nonzero element ''a'' has a unique
modular multiplicative inverse In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer is an integer such that the product is congruent to 1 with respect to the modulus .. In the standard notation of modular arithmetic this congr ...
, ''a''
−1 such that This inverse can be found by solving the congruence equation ''ax'' ≡ 1 mod ''m'', or the equivalent linear Diophantine equation
:
This equation can be solved by the Euclidean algorithm, as described
above. Finding multiplicative inverses is an essential step in the
RSA algorithm
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly ...
, which is widely used in
electronic commerce
E-commerce (electronic commerce) is the activity of electronically buying or selling of products on online services or over the Internet. E-commerce draws on technologies such as mobile commerce, electronic funds transfer, supply chain manageme ...
; specifically, the equation determines the integer used to decrypt the message. Although the RSA algorithm uses
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
s; for example, it can be used as an alternative to the
Berlekamp–Massey algorithm
The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear-feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbi ...
for decoding
BCH and
Reed–Solomon codes, which are based on Galois fields.
Chinese remainder theorem
Euclid's algorithm can also be used to solve multiple linear Diophantine equations. Such equations arise in the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, which describes a novel method to represent an integer ''x''. Instead of representing an integer by its digits, it may be represented by its remainders ''x''
''i'' modulo a set of ''N'' coprime numbers ''m''
''i'':
:
The goal is to determine ''x'' from its ''N'' remainders ''x''
''i''. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus ''M'' that is the product of all the individual moduli ''m''
''i'', and define ''M''
''i'' as
:
Thus, each ''M''
''i'' is the product of all the moduli ''except'' ''m''
''i''. The solution depends on finding ''N'' new numbers ''h''
''i'' such that
:
With these numbers ''h''
''i'', any integer ''x'' can be reconstructed from its remainders ''x''
''i'' by the equation
:
Since these numbers ''h''
''i'' are the multiplicative inverses of the ''M''
''i'', they may be found using Euclid's algorithm as described in the previous subsection.
Stern–Brocot tree
The Euclidean algorithm can be used to arrange the set of all positive
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s into an infinite
binary search tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
, called the
Stern–Brocot tree.
The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number ''a''/''b'' can be found by computing gcd(''a'',''b'') using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether ''a''/''b'' is given in lowest terms, and forms a path from the root to a node containing the number ''a''/''b''. This fact can be used to prove that each positive rational number appears exactly once in this tree.
For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:
:
The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the
Calkin–Wilf tree
In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond one-to-one to the positive rational numbers. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction has as its ...
. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.
Continued fractions
The Euclidean algorithm has a close relationship with
continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
s.
The sequence of equations can be written in the form
:
The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form
:
The third equation may be used to substitute the denominator term ''r''
1/''r''
0, yielding
:
The final ratio of remainders ''r''
''k''/''r''
''k''−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction
:
In the worked example
above, the gcd(1071, 462) was calculated, and the quotients ''q''
''k'' were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written
: