Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study.... , the Euclidean algorithm (also called Euclid's algorithm) is an algorithm
Algorithm
In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing.... to determine the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder.... (GCD) of two elements of any Euclidean domain
Euclidean domain
In abstract algebra, a Euclidean domain is a type of Ring in which the Euclidean algorithm applies. Euclidean domains possess many important properties similar to the integers: for example, the fundamental theorem of arithmetic holds in any Euclidean domain.... (for example, the integers). Its major significance is that it does not require factoring
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplication together give the original.... the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks.
Euclidean algorithm is one of the oldest algorithms known, since it appeared in Euclid's Elements
Euclid's Elements
Euclid's Elements is a mathematics and geometry treatise consisting of 13 books written by the Greek mathematics Euclid in Alexandria circa 300 BC.... around 300 BC (7th book, Proposition 2).
Discussion
Ask a question about 'Euclidean algorithm'
Start a new discussion about 'Euclidean algorithm'
Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study.... , the Euclidean algorithm (also called Euclid's algorithm) is an algorithm
Algorithm
In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing.... to determine the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , sometimes known as the greatest common factor or highest common factor , of two non-zero integers, is the largest positive integer that divisor both numbers without remainder.... (GCD) of two elements of any Euclidean domain
Euclidean domain
In abstract algebra, a Euclidean domain is a type of Ring in which the Euclidean algorithm applies. Euclidean domains possess many important properties similar to the integers: for example, the fundamental theorem of arithmetic holds in any Euclidean domain.... (for example, the integers). Its major significance is that it does not require factoring
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplication together give the original.... the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks.
History of the Euclidean algorithm
The Euclidean algorithm is one of the oldest algorithms known, since it appeared in Euclid's Elements
Euclid's Elements
Euclid's Elements is a mathematics and geometry treatise consisting of 13 books written by the Greek mathematics Euclid in Alexandria circa 300 BC.... around 300 BC (7th book, Proposition 2). Euclid originally formulated the problem geometrically, as the problem of finding the greatest common "measure" for two line lengths (a line that could be used to measure both lines without a remainder), and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. However, the algorithm was probably not discovered by Euclid
Euclid
Euclid , floruit 300 BC, also known as Euclid of Alexandria, was a Greek mathematics and is often referred to as the Father of Geometry. He was active in Alexandria during the reign of Ptolemy I .... and it may have been known up to 200 years earlier. It was almost certainly known by Eudoxus of Cnidus
Eudoxus of Cnidus
Eudoxus of Cnidus was a Ancient Greece astronomer, mathematician, scholar and student of Plato. Since all his own works are lost, our knowledge of him is obtained from secondary sources, such as Aratus's poem on astronomy.... (about 375 BC), and Aristotle
Aristotle
Aristotle was a Greeks philosopher, a student of Plato and teacher of Alexander the Great. He wrote on many subjects, including physics, metaphysics, Poetics , theater, music, logic, rhetoric, politics, government, ethics, biology and zoology.... (about 330 BC) hinted at it in his Topics, 158b, 29–35.
In mathematics, a natural number can mean either an element of the Set = *n = = ? = ? ... s a and b: check if b is zero; if yes, a is the gcd. If not, repeat the process using, respectively, b, and the remainder after dividing a by b. The remainder after dividing a by b is usually written as amod
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two numbers, and , amodulon is the remainder, on division of a by n.... b.
These algorithms can be used in any context where division with remainder is possible. This includes rings of polynomials
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the Set of polynomials in one or more variables with coefficients in a ring .... over a field
Field (mathematics)
In abstract algebra, a field is an algebraic structure with notions of addition, subtraction, multiplication and division , satisfying certain axioms.... as well as the ring of Gaussian integer
Gaussian integer
A Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i].... s, and in general all Euclidean domain
Euclidean domain
In abstract algebra, a Euclidean domain is a type of Ring in which the Euclidean algorithm applies. Euclidean domains possess many important properties similar to the integers: for example, the fundamental theorem of arithmetic holds in any Euclidean domain.... s. Applying the algorithm to the more general case other than natural numbers will be discussed in more detail later in the article.
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... , the algorithm can be expressed:
function gcd(a, b)
if b = 0 return a
elsereturn gcd(b, a mod b)
or in C/C++ as
int gcd(int a, int b)
Using iteration
An efficient, iterative method, for compilers that don't optimize tail recursion
Tail recursion
In computer science, tail recursion is a special case of Recursion_ in which the last operation of the function, the tail call, is a recursive call.... :
function gcd(a, b)
while b ? 0
t := b
b := a mod b
a := t
return a
The extended Euclidean algorithm
By keeping track of the quotients occurring during the algorithm, one can also determine integers p and q with ap + bq = gcd(a, b).
This is known as the extended Euclidean algorithm.
Original algorithm
The original algorithm as described by Euclid treated the problem geometrically, using repeated subtraction rather than mod (remainder). This algorithm is exponentially slower than the division-based algorithm in the worst case, but for small enough input values may provide a benefit on machines without a division instruction.
function gcd(a, b)
if a = 0 return b
while b ? 0
if a > b
a := a - b
else
b := b - a
return a
An example
As an example, consider computing the gcd of 1071 and 1029, which is 21.
Recall that “mod” means “the remainder after dividing.”
With the recursive algorithm:
a
b
Explanations
gcd(
1071,
1029)
The initial arguments
=
gcd(
1029,
42)
The second argument is 1071 mod 1029
=
gcd(
42,
21)
The second argument is 1029 mod 42
=
gcd(
21,
0)
The second argument is 42 mod 21
=
21
Since b=0, we return a
With the iterative algorithm:
a
b
Explanation
1071
1029
Step 1: The initial inputs
1029
42
Step 2: The remainder of 1071 divided by 1029 is 42, which is put on the right, and the divisor 1029 is put on the left.
42
21
Step 3: We repeat the loop, dividing 1029 by 42, and get 21 as remainder.
21
0
Step 4: Repeat the loop again, since 42 is divisible by 21, we get 0 as remainder, and the algorithm terminates. The number on the left, that is 21, is the gcd as required.
Observe that a ≥ b in each call. If initially, b > a, there is no problem; the first iteration effectively swaps the two values.
Proof
Suppose a and b are the natural numbers whose gcd has to be determined. Now, suppose b > 0, and the remainder of the division of a by b is r. Therefore a = qb + r where q is the quotient of the division.
Any common divisor of a and b is also a divisor of r. To see why this is true, consider that r can be written as r = a − qb. Now, if there is a common divisor d of a and b such that a = sd and b = td, then r = (s−qt)d. Since all these numbers, including s−qt, are whole numbers, it can be seen that r is divisible by d. Also b is divisible by d (this was a premise) and therefore d is a common divisor of r and b.
With the same argumentation you can see that any common divisor of r and b is also a common divisor of a and b (because a = qb + r ). Thus it follows that the set of common divisors of a and b is identical to the set of common divisors of r an b and therefore the maximum (which is the gcd) is identical.
Therefore it is enough if we continue searching for the greatest common divisor with the numbers b and r.
Since r is smaller in absolute value
Absolute value
In mathematics, the absolute value of a real number is its numerical value without regard to its Negative and non-negative numbers. So, for example, 3 is the absolute value of both 3 and -3.... than b, we will reach r = 0 after finitely many steps.
Running time
When analyzing the running time of Euclid's algorithm, the inputs requiring the most divisions are two successive Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci . Fibonacci's 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been previously described in Indian mathematics.... s (because their ratios are the convergents
Convergent (continued fraction)
A convergent is one of a sequence of values obtained by evaluating successive truncations of a continued fraction. The nth convergent is also known as the nth approximant of a continued fraction.... in the slowest continued fraction
Continued fraction
In mathematics, a continued fraction is an expression such aswhere a0 is an integer and all the other numbers ai are positive integers.... expansion to converge, that of the golden ratio
Golden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio between the sum of those quantities and the larger one is the same as the ratio between the larger one and the smaller.... ) as proved by Gabriel Lamé
Gabriel Lamé
Gabriel Lam? was a French mathematician.... , and the worst case requires O(n)
Big O notation
In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.... divisions, where n is the number of digits in the input. However, the divisions themselves are not constant time operations; the actual time complexity of the algorithm is .
The reason is that division of two n-bit numbers takes time , where m is the length of the quotient. Consider the computation of gcd(a,b) where a and b have at most n bits, let be the sequence of numbers produced by the algorithm, and let be their lengths. Then , and the running time is bounded by
This is considerably better than Euclid's original algorithm, in which the modulus operation is effectively performed using repeated subtraction in steps. Consequently, that version of the algorithm requires time for n-digit numbers, or time for the number m.
Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. An alternative algorithm, the binary GCD algorithm
Binary GCD algorithm
The binary GCD algorithm is an algorithm which computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which are cheaper when operating on the binary representation used by modern computers.... , exploits the binary
Binary numeral system
The binary numeral system, or notation with a radix of 2. Owing to its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by all modern computers.... representation used by computers to avoid divisions and thereby increase efficiency, although it too is O(n˛); it merely shrinks the constant hidden by the big-O notation on many real machines.
Computational complexity of mathematical operations
The following tables list the computational complexity of various algorithms for common mathematical operations.Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.... for more details.
Relation with continued fractions
The quotients that appear when the Euclidean algorithm is applied to the inputs a and b are precisely the numbers occurring in the continued fraction
Continued fraction
In mathematics, a continued fraction is an expression such aswhere a0 is an integer and all the other numbers ai are positive integers.... representation of a/b.
Take for instance the example of a = 1071 and b = 1029 used above.
Here is the calculation with highlighted quotients:
1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0
Consequently,
.
This method applies to arbitrary real
Real number
In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co... inputs a and nonzero b; if a/b is irrational
Irrational number
In mathematics, an irrational number is any real number that is not a rational number ? that is, it is a number which cannot be expressed as a fraction m/n, where m and n are integers, with n non-zero.... , then the Euclidean algorithm does not terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of a/b.
The quotients 1,24,2 count certain squares nested within a rectangle R having length 1071 and width 1029, in the following manner:
(1) there is 1 1029×1029 square in R whose removal leaves a 42×1029 rectangle, R1;
(2) there are 24 42×42 squares in R1 whose removal leaves a 21×42 rectangle, R2;
(3) there are 2 21×21 squares in R2 whose removal leaves nothing.
The "visual Euclidean algorithm" of nested squares applies to an arbitrary rectangle R. If the (length)/(width) of R is an irrational number, then the visual Euclidean algorithm extends to a visual continued fraction.
Generalization to Euclidean domains
The Euclidean algorithm can be applied to some rings
Ring (mathematics)
In mathematics, a ring is a type of algebraic structure. There is some variation among mathematicians as to exactly what properties a ring is required to have, as described in detail below.... , not just the integers. The most general context in which the algorithm terminates with the greatest common divisor is in a Euclidean domain
Euclidean domain
In abstract algebra, a Euclidean domain is a type of Ring in which the Euclidean algorithm applies. Euclidean domains possess many important properties similar to the integers: for example, the fundamental theorem of arithmetic holds in any Euclidean domain.... . For instance, the Gaussian integers and polynomial ring
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the Set of polynomials in one or more variables with coefficients in a ring .... s over a field
Field (mathematics)
In abstract algebra, a field is an algebraic structure with notions of addition, subtraction, multiplication and division , satisfying certain axioms.... are both Euclidean domains.
As an example, consider the ring of polynomials with rational
Rational number
In mathematics, a rational number is a number which can be expressed as a quotient of two integers. Non-integer rational numbers are usually written as the vulgar fraction , where b is not 0 .... coefficients. In this ring, division with remainder is carried out using long division
Polynomial long division
In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower Degree_of_a_polynomial, a generalised version of the familiar arithmetic technique called long division.... . The resulting polynomials are then made monic by factoring out the leading coefficient.
We calculate the greatest common divisor of
and
Following the algorithm gives these values:
a
b
This agrees with the explicit factorization. For general Euclidean domains, the proof of correctness is by induction on some size function. For the integers, this size function is just the identity. For rings of polynomials over a field, it is the degree of the polynomial (note that each step in the above table reduces the degree by at least one).
In arithmetic and number theory, the least common multiple or lowest common multiple or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple both of a and of b....
The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor of integers a and b: it also finds the integers x and y in B?zout's identity...
The binary GCD algorithm is an algorithm which computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which are cheaper when operating on the binary representation used by modern computers....
Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a rather fast greatest common divisor algorithm, an improvement on the simpler but slower Euclidean algorithm....
Cut-the-knot is an educational website maintained by Alexander Bogomolny and devoted to popular exposition of a great variety of topics in mathematics....
Cut-the-knot is an educational website maintained by Alexander Bogomolny and devoted to popular exposition of a great variety of topics in mathematics....
Cut-the-knot is an educational website maintained by Alexander Bogomolny and devoted to popular exposition of a great variety of topics in mathematics.... *
