## You are here

Homegreatest common divisor

## Primary tabs

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

## Mathematics Subject Classification

11-00*no label found*03E20

*no label found*06F25

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections