greatest common divisor


Let a and b be given integers, with at least one of them different from zero. The greatest common divisorMathworldPlanetmathPlanetmath of a and b, denoted by gcd(a,b), is the positive integer d satisfying

  1. 1.

    da and db,

  2. 2.

    if ca and cb, then cd.

More intuitively, the greatest common divisor is the largest integer dividing both a and b.

For example, gcd(345,135)=15, gcd(-7,-21)=7, gcd(18,0)=18, and gcd(44,97)=1

Given two (rational) integers, one can construct their gcd via Euclidean algorithmMathworldPlanetmath. Once the gcd is found, it can be written as a linear combinationMathworldPlanetmath of the two integers. That is, for any two integers a and b, we have gcd(a,b)=ra+sb for some integers r and s. This expression is known as the Bezout identityMathworldPlanetmath.

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 [x2,x3], a gcd for the elements x5 and x6 does not exist, for x2 and x3 are both common divisorsMathworldPlanetmathPlanetmath of x5 and x6, 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 S is a non-empty set of integers, then the gcd of S, is a positive integer d such that

  1. 1.

    da for all aS,

  2. 2.

    if ca,aS, then cd.

We denote d=gcd(S).

Remarks.

  • gcd(a,b,c)=gcd(gcd(a,b),c).

  • If TS, then gcd(S)gcd(T).

  • For any S, there is a finite subset TS such that gcd(T)=gcd(S).

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 CongruencesMathworldPlanetmathPlanetmathPlanetmath
Related topic RationalSineAndCosine
Related topic IntegralBasisOfQuadraticField
Related topic SquareRootsOfRationals
Related topic IntegerContraharmonicMeans
Related topic SubgroupsWithCoprim