|
Let  and  be given integers, with at least one of them different from zero. The greatest common divisor of  and  , denoted by  , is the positive integer  satisfying
 and  ,- if
 and  , then  .
More intuitively, the greatest common divisor is the largest integer dividing both  and  .
For example,
 ,
 ,
 , and
Given two (rational) integers, one can construct their gcd via Euclidean algorithm. Once the gcd is found, it can be written as a linear combination of the two integers. That is, for any two integers  and  , we have
 for some integers  and  . This expression is known as the Bezout identity.
One can generalize the notion of a gcd of two integers into a gcd of two elements in a commutative ring. However, given two elements in a general commutative ring, even an integral domain, a gcd may not exist. For example, in
![$ \mathbb{Z}[x^2,x^3]$](http://images.planetmath.org:8080/cache/objects/248/l2h/img23.png "$ \mathbb{Z}[x^2,x^3]$") , a gcd for the elements  and  does not exist, for  and  are both common divisors of  and  , but neither one divides another.
The idea of the gcd of two integers can be generalized in another direction: to the gcd of a non-empty set of integers. If  is a non-empty set of integers, then the
 of  , is a positive integer  such that
 for all  ,- if
 , then  .
We denote
 .
Remarks.
-
 .
- If
 , then
 .
- For any
 , there is a finite subset
 such that
 .
|
