greatest common divisor

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

1.

$d\mid a$ and $d\mid b$ ,
2.

if $c\mid a$ and $c\mid b$ , then $c\mid d$ .

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 algorithm. Once the gcd is found, it can be written as a linear combination of the two integers. That is, for any two integers $a$ and $b$ , we have $\operatorname{gcd}(a,b)=ra+sb$ for some integers $r$ and $s$ . 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}]$ , a gcd for the elements $x^{5}$ and $x^{6}$ does not exist, for $x^{2}$ and $x^{3}$ are both common divisors of $x^{5}$ and $x^{6}$ , 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 $\operatorname{gcd}$ of $S$ , is a positive integer $d$ such that

1.

$d\mid a$ for all $a\in S$ ,
2.

if $c\mid a,\forall a\in S$ , then $c\mid d$ .

We denote $d=\operatorname{gcd}(S)$ .

Remarks.

•

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

If $\varnothing\neq T\subseteq S\subseteq\mathbb{Z}$ , then $\gcd(S)\mid\gcd(T)$ .
•

For any $\varnothing\neq S\subseteq\mathbb{Z}$ , there is a finite subset $T\subseteq S$ 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	Congruences
Related topic	RationalSineAndCosine
Related topic	IntegralBasisOfQuadraticField
Related topic	SquareRootsOfRationals
Related topic	IntegerContraharmonicMeans
Related topic	SubgroupsWithCoprim