# 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. 1.

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

2. 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. 1.

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

2. 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