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$

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$

Remarks.

• $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$
• If $\varnothing\ne T\subseteq S\subseteq \mathbb{Z}$ then $\gcd(S)\mid \gcd(T)$
• For any $\varnothing\ne S\subseteq\mathbb{Z}$ there is a finite subset $T\subseteq S$ such that $\gcd(T)=\gcd(S)$