= Greatest common divisor
{title2=$\gcd$}
{wiki}
= GCD
{c}
{synonym}
For <integers> $a,b$ not both zero, their greatest common divisor is the largest positive <integer> dividing both. It is unchanged by replacing either input by its negative. The convention $\gcd(0,0)=0$ is useful, but this exceptional value is not a largest positive common <divisor>. For positive inputs, the <Euclidean algorithm> computes the answer, and <Bézout's identity> expresses it as an integer <linear combination> of the inputs.
For $12=2^2\cdot3$ and $18=2\cdot3^2$, a common <divisor> can contain at most one copy of the <prime number> two and one of the <prime number> three. Taking the smaller <prime valuation> at each <prime number> therefore gives
$$
\gcd(12,18)=2^{\min(2,1)}3^{\min(1,2)}=2\cdot3=6.
$$
The check $6=18-12$ is also a <Bézout's identity>: every common <divisor> divides this difference, and six itself divides both inputs. More generally, every common <divisor> divides the <greatest common divisor>, a stronger statement than merely being no larger than it. The companion <least common multiple> takes the larger <prime valuations>, as the diagram there illustrates. For an application, divide the <numerator> and <denominator> of the <fraction> $12/18$ by six to obtain $2/3$; these remaining <integers> are <coprime>.
Back to article page
