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 $\mathrm{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, $\mathrm{gcd}(345,135)=15$, $\mathrm{gcd}(7,21)=7$, $\mathrm{gcd}(18,0)=18$, and $\mathrm{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 $\mathrm{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 nonempty set of integers. If $S$ is a nonempty set of integers, then the $\mathrm{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=\mathrm{gcd}(S)$.
Remarks.

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

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

•
For any $\mathrm{\varnothing}\ne S\subseteq \mathbb{Z}$, there is a finite subset $T\subseteq S$ such that $\mathrm{gcd}(T)=\mathrm{gcd}(S)$.
Title  greatest common divisor 
Canonical name  GreatestCommonDivisor 
Date of creation  20130322 11:46:50 
Last modified on  20130322 11:46:50 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  22 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 1100 
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 