greatest common divisor
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 , 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 .
If , then .
For any , there is a finite subset such that .
|Title||greatest common divisor|
|Date of creation||2013-03-22 11:46:50|
|Last modified on||2013-03-22 11:46:50|
|Last modified by||CWoo (3771)|
|Synonym||greatest common factor|
|Synonym||highest common factor|