greatest common divisor
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
-
1.
and ,
-
2.
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
-
1.
for all ,
-
2.
if , then .
We denote .
Remarks.
-
•
.
-
•
If , then .
-
•
For any , there is a finite subset such that .
Title | greatest common divisor |
Canonical name | GreatestCommonDivisor |
Date of creation | 2013-03-22 11:46:50 |
Last modified on | 2013-03-22 11:46:50 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 22 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 11-00 |
Classification | msc 03E20 |
Classification | msc 06F25 |
Synonym | gcd |
Synonym | greatest common factor |
Synonym | highest common factor |
Synonym | hcf |
Related topic | GcdDomain |
Related topic | CorollaryOfBezoutsLemma |
Related topic | ExampleOfGcd |
Related topic | ExistenceAndUniquenessOfTheGcdOfTwoIntegers |
Related topic | DivisionOfCongruence |
Related topic | Congruences |
Related topic | RationalSineAndCosine |
Related topic | IntegralBasisOfQuadraticField |
Related topic | SquareRootsOfRationals |
Related topic | IntegerContraharmonicMeans |
Related topic | SubgroupsWithCoprim |