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\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)$ .