Greatest common divisor
Encyclopedia
In mathematics
, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integer
s, is the largest positive integer that divides
the numbers without a remainder
.
For example, the GCD of 8 and 12 is 4.
This notion can be extended to polynomials, see greatest common divisor of two polynomials
.
Thus the divisors of 54 are:
Similarly the divisors of 24 are:
The numbers that these two lists share in common are the common divisors of 54 and 24:
The greatest of these is 6. That is the greatest common divisor of 54 and 24. One writes:
s to be in lowest terms
. For example, gcd(42, 56) = 14, therefore,
The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2. Two numbers are called relatively prime, or coprime
if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.
Here is another concrete example, illustrated by a Venn diagram
. Suppose it is desired to find the greatest common divisor of 48 and 180. First, find the prime factorizations of the two numbers:
What they share in common is two "2"s and a "3":
, which uses the division algorithm
in combination with the observation that the gcd of two numbers also divides their difference. To compute gcd(48,18), divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Note that we ignored the quotient in each step except to notice when it reached 0, signalling that we had arrived at the answer. Formally the algorithm can be described as:
Which also could be written as
(lcm) of a and b:
Keith Slavin has shown that for odd a ≥ 1:
which is a function that can be evaluated for complex b. Wolfgang Schramm has shown that
is an entire function
in the variable b for all positive integers a where cd(k) is Ramanujan's sum. Marcelo Polezzi has shown that:
for positive integers a and b. Donald Knuth
proved the following reduction:
for non-negative integers a and b, where a and b are not both zero. More generally
which can easily be proven by considering the Euclidean algorithm in base n.
version of) the greatest common divisor problem in P
, the class of problems solvable in polynomial time. The GCD problem is not known to be in NC
, and so there is no known way to parallelize its computation across many processors; nor is it known to be P-complete
, which would imply that it is unlikely to be possible to parallelize GCD computation. In this sense the GCD problem is analogous to e.g. the integer factorization
problem, which has no known polynomial-time algorithm, but is not known to be NP-complete
. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables; if either problem is in NC or is P-complete, the other is as well. Since NC contains NL
, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.
Although the problem is not known to be in NC, parallel algorithms with time superior to the Euclidean algorithm exist; the best known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in O(n/log n) time with n1+ε processors. Randomized algorithm
s can solve the problem in O((log n)2) time on
processors (note this is superpolynomial).
for a derivation.) This result was extended in 1987 to show that the probability that k random integers has greatest common divisor d is d-k/ζ(k).
Using this information, the expected value
of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the gcd equals d is d−2/ζ(2), and since ζ(2) = π2/6 we have
This last summation is the harmonic series
, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is
For k = 3, this is approximately equal to 1.3684. For k = 4, it is approximately 1.1106.
, although in general there need not exist one for every pair of elements.
If R is a commutative ring, and a and b are in R, then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = a and d·y = b).
If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b.
Note that with this definition, two elements a and b may very well have several greatest common divisors, or none at all. If R is an integral domain then any two gcd's of a and b must be associate elements, since by definition either one must divide the other; indeed if a gcd exists, any one of its associates is a gcd as well. Existence of a gcd is not assured in arbitrary integral domains. However if R is a unique factorization domain
, then any two elements have a gcd, and more generally this is true in gcd domain
s.
If R is a Euclidean domain
in which euclidean division is given algorithmically (as is the case for instance when R = F[X] where F is a field
, or when R is the ring of Gaussian integer
s), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.
The following is an example of an integral domain with two elements that do not have a gcd:
The elements 2 and 1 + √(−3) are two "maximal common divisors" (i.e. any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √(−3)), but they are not associated, so there is no greatest common divisor of a and b.
Corresponding to the Bezout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring. This is the ideal
generated by a and b, and is denoted simply (a, b). In a ring all of whose ideals are principal (a principal ideal domain
or PID), this ideal will be identical with the set of multiples of some ring element d; then this d is a greatest common divisor of a and b. But the ideal (a, b) can be useful even when there is no greatest common divisor of a and b. (Indeed, Ernst Kummer
used this ideal as a replacement for a gcd in his treatment of Fermat's Last Theorem
, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d, whence the ring-theoretic term.)
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s, is the largest positive integer that divides
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
the numbers without a remainder
Remainder
In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
.
For example, the GCD of 8 and 12 is 4.
This notion can be extended to polynomials, see greatest common divisor of two polynomials
Greatest common divisor of two polynomials
Informally, the greatest common divisor of two polynomials p and q is the largest polynomial that divides both p and q evenly. The definition is modeled on the concept of the greatest common divisor of two integers, the greatest integer that divides both...
.
Example
The number 54 can be expressed as a product of two other integers in several different ways:
Thus the divisors of 54 are:
Similarly the divisors of 24 are:
The numbers that these two lists share in common are the common divisors of 54 and 24:
The greatest of these is 6. That is the greatest common divisor of 54 and 24. One writes:
Reducing fractions
The greatest common divisor is useful for reducing fractionFraction (mathematics)
A fraction represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, we specify how many parts of a certain size there are, for example, one-half, five-eighths and three-quarters.A common or "vulgar" fraction, such as 1/2, 5/8, 3/4, etc., consists...
s to be in lowest terms
Irreducible fraction
An irreducible fraction is a vulgar fraction in which the numerator and denominator are smaller than those in any other equivalent vulgar fraction...
. For example, gcd(42, 56) = 14, therefore,
The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2. Two numbers are called relatively prime, or coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.
A geometric view
For example, 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 greatest common divisor 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).Using prime factorizations
Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18, 84), we find the prime factorizations 18 = 2 · 32 and 84 = 22 · 3 · 7 and notice that the "overlap" of the two expressions is 2 · 3; so gcd(18, 84) = 6. In practice, this method is only feasible for small numbers; computing prime factorizations in general takes far too long.Here is another concrete example, illustrated by a Venn diagram
Venn diagram
Venn diagrams or set diagrams are diagrams that show all possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...
. Suppose it is desired to find the greatest common divisor of 48 and 180. First, find the prime factorizations of the two numbers:
- 48 = 2 × 2 × 2 × 2 × 3,
- 180 = 2 × 2 × 3 × 3 × 5.
What they share in common is two "2"s and a "3":
- Least common multiple = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720
- Greatest common divisor = 2 × 2 × 3 = 12.
Using Euclid's algorithm
A much more efficient method is the Euclidean algorithmEuclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
, which uses the division algorithm
Division algorithm
In mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be specified precisely by a theorem stating that these exist uniquely with given properties. An integer division algorithm is any effective method for producing...
in combination with the observation that the gcd of two numbers also divides their difference. To compute gcd(48,18), divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Note that we ignored the quotient in each step except to notice when it reached 0, signalling that we had arrived at the answer. Formally the algorithm can be described as:
Which also could be written as
Other methods
If a and b are not both zero, the greatest common divisor of a and b can be computed by using least common multipleLeast common multiple
In arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
(lcm) of a and b:
Keith Slavin has shown that for odd a ≥ 1:
which is a function that can be evaluated for complex b. Wolfgang Schramm has shown that
is an entire function
Entire function
In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic over the whole complex plane...
in the variable b for all positive integers a where cd(k) is Ramanujan's sum. Marcelo Polezzi has shown that:
for positive integers a and b. Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
proved the following reduction:
for non-negative integers a and b, where a and b are not both zero. More generally
which can easily be proven by considering the Euclidean algorithm in base n.
Complexity
The existence of the Euclidean algorithm places (the decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
version of) the greatest common divisor problem in P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
, the class of problems solvable in polynomial time. The GCD problem is not known to be in NC
NC (complexity)
In complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O using O parallel processors...
, and so there is no known way to parallelize its computation across many processors; nor is it known to be P-complete
P-complete
In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:# which problems are difficult to parallelize effectively, and;# which problems are difficult to solve in limited space....
, which would imply that it is unlikely to be possible to parallelize GCD computation. In this sense the GCD problem is analogous to e.g. the integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
problem, which has no known polynomial-time algorithm, but is not known to be NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables; if either problem is in NC or is P-complete, the other is as well. Since NC contains NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.
Although the problem is not known to be in NC, parallel algorithms with time superior to the Euclidean algorithm exist; the best known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in O(n/log n) time with n1+ε processors. Randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
s can solve the problem in O((log n)2) time on
processors (note this is superpolynomial).Properties
- Every common divisor of a and b is a divisor of gcd(a, b).
- gcd(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a·p + b·q where p and q are integers. This expression is called Bézout's identityBézout's identityIn number theory, Bézout's identity for two integers a, b is an expressionwhere x and y are integers , such that d is a common divisor of a and b. Bézout's lemma states that such coefficients exist for every pair of nonzero integers...
. Numbers p and q like this can be computed with the extended Euclidean algorithmExtended Euclidean algorithmThe extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
. - gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|. This is usually used as the base case in the Euclidean algorithm.
- If a divides the product b·c, and gcd(a, b) = d, then a/d divides c.
- If m is a non-negative integer, then gcd(m·a, m·b) = m·gcd(a, b).
- If m is any integer, then gcd(a + m·b, b) = gcd(a, b).
- If m is a nonzero common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.
- The gcd is a multiplicative functionMultiplicative functionIn number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
in the following sense: if a1 and a2 are relatively prime, then gcd(a1·a2, b) = gcd(a1, b)·gcd(a2, b). - The gcd is a commutativeCommutativityIn mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
function: gcd(a, b) = gcd(b, a). - The gcd is an associativeAssociativityIn mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c). - The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers.
- gcd(a, b) is closely related to the least common multipleLeast common multipleIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
lcm(a, b): we have
-
- gcd(a, b)·lcm(a, b) = a·b.
- This formula is often used to compute least common multiples: one first computes the gcd with Euclid's algorithm and then divides the product of the given numbers by their gcd.
- The following versions of distributivityDistributivityIn mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
hold true:
- gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
- lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).
- It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s become a completeComplete latticeIn mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
distributiveDistributive latticeIn mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
latticeLattice (order)In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. - In a Cartesian coordinate systemCartesian coordinate systemA Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...
, gcd(a, b) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and (a, b), excluding (0, 0).
- It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural number
- The following versions of distributivity
Probabilities and expected value
In 1972, James E. Nymann showed that the probability that k independently chosen integers are coprime is 1/ζ(k). (See coprimeCoprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
for a derivation.) This result was extended in 1987 to show that the probability that k random integers has greatest common divisor d is d-k/ζ(k).
Using this information, the expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the gcd equals d is d−2/ζ(2), and since ζ(2) = π2/6 we have
This last summation is the harmonic series
Harmonic series (mathematics)
In mathematics, the harmonic series is the divergent infinite series:Its name derives from the concept of overtones, or harmonics in music: the wavelengths of the overtones of a vibrating string are 1/2, 1/3, 1/4, etc., of the string's fundamental wavelength...
, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is
For k = 3, this is approximately equal to 1.3684. For k = 4, it is approximately 1.1106.
The gcd in commutative rings
The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ringCommutative ring
In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra....
, although in general there need not exist one for every pair of elements.
If R is a commutative ring, and a and b are in R, then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = a and d·y = b).
If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b.
Note that with this definition, two elements a and b may very well have several greatest common divisors, or none at all. If R is an integral domain then any two gcd's of a and b must be associate elements, since by definition either one must divide the other; indeed if a gcd exists, any one of its associates is a gcd as well. Existence of a gcd is not assured in arbitrary integral domains. However if R is a unique factorization domain
Unique factorization domain
In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
, then any two elements have a gcd, and more generally this is true in gcd domain
GCD domain
In mathematics, a GCD domain is an integral domain R with the property that any two non-zero elements have a greatest common divisor . Equivalently, any two non-zero elements of R have a least common multiple ....
s.
If R is a Euclidean domain
Euclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
in which euclidean division is given algorithmically (as is the case for instance when R = F[X] where F is a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
, or when R is the ring of Gaussian integer
Gaussian integer
In number theory, 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]. The Gaussian integers are a special case of the quadratic...
s), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.
The following is an example of an integral domain with two elements that do not have a gcd:
The elements 2 and 1 + √(−3) are two "maximal common divisors" (i.e. any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √(−3)), but they are not associated, so there is no greatest common divisor of a and b.
Corresponding to the Bezout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring. This is the ideal
Ideal (ring theory)
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....
generated by a and b, and is denoted simply (a, b). In a ring all of whose ideals are principal (a principal ideal domain
Principal ideal domain
In abstract algebra, 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, although some authors refer to PIDs as...
or PID), this ideal will be identical with the set of multiples of some ring element d; then this d is a greatest common divisor of a and b. But the ideal (a, b) can be useful even when there is no greatest common divisor of a and b. (Indeed, Ernst Kummer
Ernst Kummer
Ernst Eduard Kummer was a German mathematician. Skilled in applied mathematics, Kummer trained German army officers in ballistics; afterwards, he taught for 10 years in a gymnasium, the German equivalent of high school, where he inspired the mathematical career of Leopold Kronecker.-Life:Kummer...
used this ideal as a replacement for a gcd in his treatment of Fermat's Last Theorem
Fermat's Last Theorem
In number theory, Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two....
, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d, whence the ring-theoretic term.)
See also
- CoprimeCoprimeIn number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
- Least common multipleLeast common multipleIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
- Lowest common denominatorLowest common denominatorIn mathematics, the lowest common denominator or least common denominator is the least common multiple of the denominators of a set of vulgar fractions...
- Binary GCD algorithmBinary GCD algorithmThe binary GCD algorithm, also known as Stein's algorithm, is an algorithm that 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...
- Euclidean algorithmEuclidean algorithmIn mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
- Extended Euclidean algorithmExtended Euclidean algorithmThe extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
- Greatest common divisor of two polynomialsGreatest common divisor of two polynomialsInformally, the greatest common divisor of two polynomials p and q is the largest polynomial that divides both p and q evenly. The definition is modeled on the concept of the greatest common divisor of two integers, the greatest integer that divides both...
Further reading
- Donald KnuthDonald KnuthDonald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp. 333–356. - Thomas H. CormenThomas H. CormenThomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College and currently Chair of the Dartmouth College Department of Computer Science. Between 2004 and 2008 he directed...
, Charles E. LeisersonCharles E. LeisersonCharles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language...
, Ronald L. Rivest, and Clifford SteinClifford SteinClifford Stein, a computer scientist, is currently a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science. Stein is chair of the Industrial Engineering and Operations Research...
. Introduction to AlgorithmsIntroduction to AlgorithmsIntroduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities. It is also one of the most commonly cited references for algorithms in published papers, with over 4600...
, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp. 856–862. - Saunders MacLane and Garrett BirkhoffGarrett BirkhoffGarrett Birkhoff was an American mathematician. He is best known for his work in lattice theory.The mathematician George Birkhoff was his father....
. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: "The Euclidean Algorithm."
External links
- greatest common divisor at Everything2.com
- Greatest Common Measure: The Last 2500 Years, by Alexander StepanovAlexander StepanovAlexander Alexandrovich Stepanov is the primary designer and implementer of the C++ Standard Template Library, which he started to develop around 1992 while employed at HP Labs...