HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s, which are not all zero, is the largest positive integer that
divides In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...
each of the integers. For two integers , , the greatest common divisor of and is denoted \gcd (x,y). For example, the GCD of 8 and 12 is 4, that is, . In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include highest common factor, etc. Historically, other names for the same concept have included greatest common measure. This notion can be extended to polynomials (see ''
Polynomial greatest common divisor In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common d ...
'') and other
commutative ring In mathematics, a commutative ring is a Ring (mathematics), ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring prope ...
s (see ' below).


Overview


Definition

The ''greatest common divisor'' (GCD) of
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s and , at least one of which is nonzero, is the greatest
positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
such that is a
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...
of both and ; that is, there are integers and such that and , and is the largest such integer. The GCD of and is generally denoted . When one of and is zero, the GCD is the absolute value of the nonzero integer: . This case is important as the terminating step of the
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is a ...
. The above definition is unsuitable for defining , since there is no greatest integer such that . However, zero is its own greatest divisor if ''greatest'' is understood in the context of the divisibility relation, so is commonly defined as . This preserves the usual identities for GCD, and in particular
Bézout's identity In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is the following theorem: Here the greatest common divisor of and is taken to be . The integers and are called B� ...
, namely that generates the same ideal as . This convention is followed by many
computer algebra system A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...
s. Nonetheless, some authors leave undefined. The GCD of and is their greatest positive common divisor in the
preorder In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive relation, reflexive and Transitive relation, transitive. The name is meant to suggest that preorders are ''almost'' partial orders, ...
relation of
divisibility In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a ''Multiple (mathematics), multiple'' of m. An integer n is divis ...
. This means that the common divisors of and are exactly the divisors of their GCD. This is commonly proved by using either
Euclid's lemma In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers: 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 well. In ...
, the
fundamental theorem of arithmetic In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 is prime or can be represented uniquely as a product of prime numbers, ...
, or the
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is a ...
. This is the meaning of "greatest" that is used for the generalizations of the concept of GCD.


Example

The number 54 can be expressed as a product of two integers in several different ways: : 54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. Thus the complete list of ''divisors'' of 54 is 1, 2, 3, 6, 9, 18, 27, 54. Similarly, the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24. The numbers that these two lists have ''in common'' are the ''common divisors'' of 54 and 24, that is, : 1, 2, 3, 6. Of these, the greatest is 6, so it is the ''greatest common divisor'': : \gcd(54,24) = 6. Computing all divisors of the two numbers in this way is usually not efficient, especially for large numbers that have many divisors. Much more efficient methods are described in '.


Coprime numbers

Two numbers are called relatively prime, or
coprime In number theory, 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 equiv ...
, if their greatest common divisor equals . For example, 9 and 28 are coprime.


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 thus be divided into a grid of 12-by-12 squares, with two squares along one edge () and five squares along the other ().


Applications


Reducing fractions

The greatest common divisor is useful for reducing
fraction A fraction (from , "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-fifths, thre ...
s to the lowest terms. For example, , therefore, : \frac=\frac=\frac.


Least common multiple

The least common multiple of two integers that are not both zero can be computed from their greatest common divisor, by using the relation : \operatorname(a,b)=\frac.


Calculation


Using prime factorizations

Greatest common divisors can be computed by determining the
prime factorization In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
s of the two numbers and comparing factors. For example, to compute , we find the prime factorizations 48 = 24 · 31 and 180 = 22 · 32 · 51; the GCD is then 2min(4,2) · 3min(1,2) · 5min(0,1) = 22 · 31 · 50 = 12 The corresponding LCM is then 2max(4,2) · 3max(1,2) · 5max(0,1) = 24 · 32 · 51 = 720. In practice, this method is only feasible for small numbers, as computing prime factorizations takes too long.


Euclid's algorithm

The method introduced by
Euclid Euclid (; ; BC) was an ancient Greek mathematician active as a geometer and logician. Considered the "father of geometry", he is chiefly known for the '' Elements'' treatise, which established the foundations of geometry that largely domina ...
for computing greatest common divisors is based on the fact that, given two positive integers and such that , the common divisors of and are the same as the common divisors of and . So, Euclid's method for computing the greatest common divisor of two positive integers consists of replacing the larger number with the difference of the numbers, and repeating this until the two numbers are equal: that is their greatest common divisor. For example, to compute , one proceeds as follows: : \begin\gcd(48,18)\quad&\to\quad \gcd(48-18, 18)= \gcd(30,18)\\ &\to \quad \gcd(30-18, 18)= \gcd(12,18)\\ &\to \quad \gcd(12,18-12)= \gcd(12,6)\\ &\to \quad \gcd(12-6,6)= \gcd(6,6).\end So . This method can be very slow if one number is much larger than the other. So, the variant that follows is generally preferred.


Euclidean algorithm

A more efficient method is the ''Euclidean algorithm'', a variant in which the difference of the two numbers and is replaced by the ''remainder'' 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 ...
(also called ''division with remainder'') of by . Denoting this remainder as , the algorithm replaces with repeatedly until the pair is , where is the greatest common divisor. For example, to compute gcd(48,18), the computation is as follows: : \begin\gcd(48,18)\quad&\to\quad \gcd(18, 48\bmod 18)= \gcd(18, 12)\\ &\to \quad \gcd(12, 18\bmod 12)= \gcd(12,6)\\ &\to \quad \gcd(6,12\bmod 6)= \gcd(6,0).\end This again gives .


Binary GCD algorithm

The binary GCD algorithm is a variant of Euclid's algorithm that is specially adapted to the binary representation of the numbers, which is used in most
computers A computer is a machine that can be programmed to automatically carry out sequences of arithmetic or logical operations ('' computation''). Modern digital electronic computers can perform generic sets of operations known as ''programs'', ...
. The binary GCD algorithm differs from Euclid's algorithm essentially by dividing by two every even number that is encountered during the computation. Its efficiency results from the fact that, in binary representation, testing parity consists of testing the right-most digit, and dividing by two consists of removing the right-most digit. The method is as follows, starting with and that are the two positive integers whose GCD is sought. # If and are both even, then divide both by two until at least one of them becomes odd; let be the number of these paired divisions. # If is even, then divide it by two until it becomes odd. # If is even, then divide it by two until it becomes odd. #: Now, and are both odd and will remain odd until the end of the computation # While do #* If , then replace with and divide the result by two until becomes odd (as and are both odd, there is, at least, one division by 2). #* If , then replace with and divide the result by two until becomes odd. # Now, , and the greatest common divisor is 2^d a. Step 1 determines as the highest power of that divides and , and thus their greatest common divisor. None of the steps changes the set of the odd common divisors of and . This shows that when the algorithm stops, the result is correct. The algorithm stops eventually, since each steps divides at least one of the operands by at least . Moreover, the number of divisions by and thus the number of subtractions is at most the total number of digits. Example: (''a'', ''b'', ''d'') = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; the original GCD is thus the product 6 of and . The binary GCD algorithm is particularly easy to implement and particularly efficient on binary computers. Its
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
is : O((\log a + \log b)^2). The square in this complexity comes from the fact that division by and subtraction take a time that is proportional to the number of bits of the input. The computational complexity is usually given in terms of the length of the input. Here, this length is , and the complexity is thus : O(n^2).


Lehmer's GCD algorithm

Lehmer's algorithm is based on the observation that the initial quotients produced by Euclid's algorithm can be determined based on only the first few digits; this is useful for numbers that are larger than a computer word. In essence, one extracts initial digits, typically forming one or two computer words, and runs Euclid's algorithms on these smaller numbers, as long as it is guaranteed that the quotients are the same with those that would be obtained with the original numbers. The quotients are collected into a small 2-by-2 transformation matrix (a matrix of single-word integers) to reduce the original numbers. This process is repeated until numbers are small enough that the binary algorithm (see below) is more efficient. This algorithm improves speed, because it reduces the number of operations on very large numbers, and can use hardware arithmetic for most operations. In fact, most of the quotients are very small, so a fair number of steps of the Euclidean algorithm can be collected in a 2-by-2 matrix of single-word integers. When Lehmer's algorithm encounters a quotient that is too large, it must fall back to one iteration of Euclidean algorithm, with a
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 ...
of large numbers.


Other methods

If and are both nonzero, the greatest common divisor of and can be computed by using
least common multiple In arithmetic and number theory, the least common multiple (LCM), lowest common multiple, or smallest common multiple (SCM) of two integers ''a'' and ''b'', usually denoted by , is the smallest positive integer that is divisible by both ''a'' and ...
(LCM) of and : : \gcd(a,b)=\frac, but more commonly the LCM is computed from the GCD. Using
Thomae's function Thomae's function is a real-valued function of a real variable that can be defined as: f(x) = \begin \frac &\textx = \tfrac\quad (x \text p \in \mathbb Z \text q \in \mathbb N \text\\ 0 &\textx \text \end It is named after Carl ...
, : \gcd(a,b) = a f\left(\frac b a\right), which generalizes to and
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 (for example, The set of all ...
s or commensurable real numbers. Keith Slavin has shown that for odd : : \gcd(a,b)=\log_2\prod_^ (1+e^) which is a function that can be evaluated for complex ''b''. Wolfgang Schramm has shown that : \gcd(a,b)=\sum\limits_^a \exp (2\pi ikb/a) \cdot \sum\limits_ \frac is an
entire function In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic on the whole complex plane. Typical examples of entire functions are polynomials and the exponential function, and any ...
in the variable ''b'' for all positive integers ''a'' where ''c''''d''(''k'') is Ramanujan's sum.


Complexity

The
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
of the computation of greatest common divisors has been widely studied. If one uses the
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is a ...
and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most bits is . This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication. However, if a fast multiplication algorithm is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication. More precisely, if the multiplication of two integers of bits takes a time of , then the fastest known algorithm for greatest common divisor has a complexity . This implies that the fastest known algorithm has a complexity of . Previous complexities are valid for the usual
models of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
, specifically multitape Turing machines and
random-access machine In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capab ...
s. The computation of the greatest common divisors belongs thus to the class of problems solvable in quasilinear time. ''A fortiori'', the corresponding
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
belongs to the class P 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 it efficiently; nor is it known to be
P-complete In computational complexity theory, a decision problem is P-complete ( complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. The notion of P-complete decision problems is use ...
, which would imply that it is unlikely to be possible to efficiently parallelize GCD computation. 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 An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
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 asymptotically faster than the Euclidean algorithm exist; the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in time with processors.
Randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s can solve the problem in time on \exp\left(O\left(\sqrt\right)\right) processors (this is superpolynomial).


Properties

* For positive integers , . * Every common divisor of and is a divisor of . * , 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 , where ''p'' and ''q'' are integers. This expression is called
Bézout's identity In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout who proved it for polynomials, is the following theorem: Here the greatest common divisor of and is taken to be . The integers and are called B� ...
. Numbers ''p'' and ''q'' like this can be computed with 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 id ...
. * , for , since any number is a divisor of 0, and the greatest divisor of ''a'' is . This is usually used as the base case in the Euclidean algorithm. * If ''a'' divides the product ''b''⋅''c'', and , then ''a''/''d'' divides ''c''. * If ''m'' is a positive integer, then . * If ''m'' is any integer, then . Equivalently, . * If ''m'' is a positive common divisor of ''a'' and ''b'', then . * If , then . * The GCD is a
commutative 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. Perhaps most familiar as a pr ...
function: . * The GCD is an
associative In mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for express ...
function: . Thus can be used to denote the GCD of multiple arguments. * The GCD is a
multiplicative function In number theory, a multiplicative function is an arithmetic function f of a positive integer n with the property that f(1)=1 and f(ab) = f(a)f(b) whenever a and b are coprime. An arithmetic function is said to be completely multiplicative (o ...
in the following sense: if ''a''1 and ''a''2 are relatively prime, then . * is closely related to the
least common multiple In arithmetic and number theory, the least common multiple (LCM), lowest common multiple, or smallest common multiple (SCM) of two integers ''a'' and ''b'', usually denoted by , is the smallest positive integer that is divisible by both ''a'' and ...
: we have *: . : 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
distributivity In mathematics, the distributive property of binary operations is a generalization of 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 ...
hold true: *: *: . * If we have the unique prime factorizations of and where and , then the GCD of ''a'' and ''b'' is *: . * It is sometimes useful to define and because then the
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s become a complete
distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...
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 system In geometry, a Cartesian coordinate system (, ) in a plane (geometry), plane is a coordinate system that specifies each point (geometry), point uniquely by a pair of real numbers called ''coordinates'', which are the positive and negative number ...
, can be interpreted as the number of segments between points with integral coordinates on the straight
line segment In geometry, a line segment is a part of a line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
joining the points and . * For non-negative integers and , where and are not both zero, provable by considering the Euclidean algorithm in base ''n'': *: . * An identity involving
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
: *: \gcd(a,b) = \sum_ \varphi(k) . * GCD Summatory function (Pillai's arithmetical function): \sum_^n \gcd(k,n) = \sum_ d \varphi \left( \frac n d \right) =n\sum_\frac =n\prod_\left(1+\nu_p(n)\left(1-\frac\right)\right) where \nu_p(n) is the -adic valuation.


Probabilities and expected value

In 1972, James E. Nymann showed that integers, chosen independently and uniformly from , are coprime with probability as goes to infinity, where refers to the
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for and its analytic c ...
. (See
coprime In number theory, 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 equiv ...
for a derivation.) This result was extended in 1987 to show that the probability that random integers have greatest common divisor is . Using this information, the
expected value In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...
of the greatest common divisor function can be seen (informally) to not exist when . In this case the probability that the GCD equals is , and since we have : \mathrm( \mathrm ) = \sum_^\infty d \frac = \frac \sum_^\infty \frac. This last summation is the harmonic series, which diverges. However, when , the expected value is well-defined, and by the above argument, it is : \mathrm(k) = \sum_^\infty d^ \zeta(k)^ = \frac. For , this is approximately equal to 1.3684. For , it is approximately 1.1106.


In commutative rings

The notion of greatest common divisor can more generally be defined for elements of an arbitrary
commutative ring In mathematics, a commutative ring is a Ring (mathematics), ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring prope ...
, although in general there need not exist one for every pair of elements. * If is a commutative ring, and and are in , then an element of is called a ''common divisor'' of and if it divides both and (that is, if there are elements and in such that ''d''·''x'' = ''a'' and ''d''·''y'' = ''b''). * If is a common divisor of and , and every common divisor of and divides , then is called a ''greatest common divisor'' of and ''b''. With this definition, two elements and may very well have several greatest common divisors, or none at all. If is an
integral domain In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibilit ...
, then any two GCDs of and must be
associate elements In mathematics, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibility ...
, 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 is a
unique factorization domain 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 ...
or any other
GCD domain In mathematics, a GCD domain (sometimes called just domain) is an integral domain ''R'' with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated ...
, then any two elements have a GCD. If is a
Euclidean domain In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of Euclidean division of integers. Th ...
in which euclidean division is given algorithmically (as is the case for instance when where is a field, or when is the ring 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 ...
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: : R = \mathbb\left sqrt\,\,\right\quad a = 4 = 2\cdot 2 = \left(1+\sqrt\,\,\right)\left(1-\sqrt\,\,\right),\quad b = \left(1+\sqrt\,\,\right)\cdot 2. The elements and are two maximal common divisors (that is, any common divisor which is a multiple of is associated to , the same holds for , but they are not associated, so there is no greatest common divisor of and . Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form , where and range over the ring. This is the ideal generated by and , and is denoted simply . In a ring all of whose ideals are principal (a
principal ideal domain In mathematics, a principal ideal domain, or PID, is an integral domain (that is, a non-zero commutative ring without nonzero zero divisors) in which every ideal is principal (that is, is formed by the multiples of a single element). Some author ...
or PID), this ideal will be identical with the set of multiples of some ring element ; then this is a greatest common divisor of and . But the ideal can be useful even when there is no greatest common divisor of and . (Indeed,
Ernst Kummer Ernst Eduard Kummer (29 January 1810 – 14 May 1893) 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 h ...
used this ideal as a replacement for a GCD in his treatment of
Fermat's Last Theorem In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive number, positive integers , , and satisfy the equation for any integer value of greater than . The cases ...
, although he envisioned it as the set of multiples of some hypothetical, or ''ideal'', ring element , whence the ring-theoretic term.)


See also

*
Bézout domain In mathematics, a Bézout domain is an integral domain in which the sum of two principal ideals is also a principal ideal. This means that Bézout's identity holds for every pair of elements, and that every finitely generated ideal is principal. ...
*
Lowest common denominator In mathematics, the lowest common denominator or least common denominator (abbreviated LCD) is the lowest common multiple of the denominators of a set of fractions. It simplifies adding, subtracting, and comparing fractions. Description The l ...
*
Unitary divisor In mathematics, a natural number ''a'' is a unitary divisor (or Hall divisor) of a number ''b'' if ''a'' is a divisor of ''b'' and if ''a'' and \frac are coprime, having no common factor other than 1. Equivalently, a divisor ''a'' of ''b'' is a un ...


Notes


References

* * * *


Further reading

*
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
. ''
The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4 ...
'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. . Section 4.5.2: The Greatest Common Divisor, pp. 333–356. * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
Clifford Stein Clifford Seth Stein (born December 14, 1965), a computer scientist, is 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 Scien ...
. ''
Introduction to Algorithms ''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ron Rivest, Ronald L. Rivest, and Clifford Stein. The book is described by its publisher as "the leading algorithms text in universities w ...
'', Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.2: Greatest common divisor, pp. 856–862. *
Saunders Mac Lane Saunders Mac Lane (August 4, 1909 – April 14, 2005), born Leslie Saunders MacLane, was an American mathematician who co-founded category theory with Samuel Eilenberg. Early life and education Mac Lane was born in Norwich, Connecticut, near w ...
and
Garrett Birkhoff Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory. The mathematician George Birkhoff (1884–1944) was his father. Life The son of the mathematician Ge ...
. ''A Survey of Modern Algebra'', Fourth Edition. MacMillan Publishing Co., 1977. . 1–7: "The Euclidean Algorithm."


External links

* gcd(x,y) = y function graph: https://www.desmos.com/calculator/6nizzenog5 {{Number-theoretic algorithms Multiplicative functions Articles containing video clips