Greatest common divisor

Definitions

  • The greatest common divisor (GCD or g.c.d.) of two (or more) numbers is the largest integer by which they can be divided.
  • There is always a common divisor of \(1\).
  • If the GCD of two (or more) numbers is \(1\), they are called coprime.
  • Every two prime numbers are also coprime, but not every two coprime numbers are prime.

Algorithm

  1. We factorize each number into its primes;
  2. We take only those primes that are common to all numbers; and
  3. We take them with the lowest power.
  4. The GCD is the product of those primes raised to their lowest powers.
Example: Finding GCD of two numbers

To find the GCD of \(48\) and \(90\), we express each of them as the product of primes

\begin{align} 48&=2^4\times 3 \\ 18&=2\times 3^2\times 5 \end{align}

Only \(2\) and \(3\) are common to both numbers, so only those are considered. The lowest power of \(2\) is \(1\), and the lowest power of \(3\) is also \(1\). Therefore,

\[\operatorname{GCD}(48,90)=2^1\times 3^1=6\]
Important Note

Although we may be able to guess the GCD for small numbers relatively easily, a systematic approach is necessary when working with larger numbers or a lot of numbers.

Example: Finding GCD of three numbers

To find the GCD of \(600\), \(900\) and \(945\), we express each of them as the product of primes

\begin{align} 600&=2^3\times 3\times 5^2 \\ 900&=2^2\times 3^2\times 5^2 \\ 945&=3^3\times 5\times 7 \end{align}

Only \(3\) and \(5\) are common to all numbers, so only those are considered. The lowest power of \(3\) is \(1\), and the lowest power of \(5\) is also \(1\). Therefore,

\[\operatorname{GCD}(600,900,945)=3^1\times 5^1=15\]

GCD for symbolic expressions

The same principles are followed if we want to get the GCD of two (or more) expressions with unknowns (i.e., placeholder letters) in them.

Example: Finding GCD of two expressions

To find the GCD of \(6x^2y^3\) and \(9x^3yz^2\), we express each of them as the product of irreducible factors.

\begin{align} 6x^2y^3&=2\times 3\times x^2\times y^3 \\ 9x^3yz^2&=3^2\times x^3\times y\times z^2 \end{align}

For numeric coefficients, only \(3\) is common, and its lowest power is \(1\). For symbols, both \(x\) and \(y\) are common. The lowest power of \(x\) is \(2\), and that of \(y\) is \(1\). Therefore,

\[\operatorname{GCD}(6x^2y^3,9x^3yz^2)=3\times x^2\times y=3x^2y\]

Uses of the GCD

It is typically used in simplifying rational numbers and factoring expressions, in addition to several other important uses. For example to simplify the rational number \(\frac{504}{784}\), we factorize its numerator and denominator to find out that \begin{align}\require{cancel} 504&=2^3\times 3^2\times 7 \\ 784&=2^4\times 7^2 \end{align}

The GCD of those numbers is \(2^3\times 7\). Therefore, we can write the rational number as \[\dfrac{504}{784}=\dfrac{2^3\times 3^2\times 7}{2^4\times 7^2}=\dfrac{\cancel{2^3}\times\cancel{7}\times 3^2}{\cancel{2^3}\times\cancel{7}\times 2^1\times 7^1}=\dfrac{3^2}{2\times 7}=\dfrac{9}{14}\]