Greatest common divisor and least common multiple

Greatest common divisor (gcd)

The numerator and the denominator of a fraction can have the same prime factors in common. When a fraction is reduced, common factors (aka common divisors) are canceled out. This is what we learned in the last chapter. The total factor canceled out when a fraction is reduced to lowest terms is the greatest common divisor (gcd) (aka greatest common factor or highest common divisor/factor). Thus, the gcd of two (or more) given integers is the largest integer that divides each of the given integers.

The greatest factor that 30 and 45 have in common is 15. By dividing both the numerator and denominator by their gcd, a fraction can be reduced to lowest terms.

If the given integers do not share any prime factors, their gcd equals 1. The only integer factor they have in common is 1. The numerator and the denominator both divided by their gcd yields a fraction in its lowest terms (like 2/3 in the example above). If a fraction is in lowest terms, the gcd of the numerator and denominator is 1. For example, $\frac{6}{35}$ is in lowest terms:

If one (or both) of the arguments is 1 or a prime number, the gcd is 1, unless one of the arguments is 0, because if one of the arguments is 0, the gcd is the other argument.

Euclidean algorithm

So far we (prime) factorized the integers to find the gcd. This is fundamentally correct, but not always most efficient. Factorizing larger numbers may require a fair amount of arithmetic. An efficient way to find the gcd of two integers is the famous Euclidean algorithm (c. 300 BCE).

The recipe is to divide the greatest of two integers by the smallest, divide the smallest by the remainder, divide the remainder by the new remainder and so on, until the new remainder is zero. The second last remainder is the gcd of the two initial integers. Next examples, using long division, will make things clear:

By dividing both the numerator and denominator by their gcd, a fraction can be reduced to lowest terms:

In JavaScript:

function gcd(a, b){
  [b,a] = [a,b].sort(() => a - b);
  let oldR = a,
      newR = b,
	  t;
  while (newR !== 0) { // while newRemainder ≠ 0
    t = newR;
    newR = oldR%newR; // newRemainder = oldRemainder mod newRemainder
    oldR = t;
  }
  return oldR;
}

gcd(7,91); // returns: 7

Appendix A provides a proof of why the Euclidean algorithm works.

Least common multiple (lcm)

When fractions are added or subtracted, they need to have equal denominators. Fractions with unequal denominators need to be converted to the same denominator first. In the last chapter this was accomplished by applying rule 5. This always works, but is not always most efficient.

$$\begin{array}{l}\frac{1}{2}+\frac{5}{6}=\frac{6}{12}+\frac{10}{12}=\frac{16}{12}\\ \phantom{\frac{16}{12}}=\frac{4\times <!--\; \times \; -->4}{4\times <!--\; \times \; -->3}=\frac{4}{3}=1⁤<!--\; INVISIBLE\; PLUS\; -->\frac{1}{3}\end{array}$$

In the above example, 12 is a multiple of both 2 and 6. The new denominator 12 is a common multiple of the initial denominators, but not the least common multiple (lcm) (aka smallest common multiple or lowest common multiple). The lcm of 2 and 6 is 6.

In the example above, a "reverse reduction" is applied to 1/2. Rule 3 is used to convert 1/2 to 3/6. To convert denominator 2 to the new common denominator 6, it needs to be multiplied by 3. In order to retain an equal fraction, also the numerator needs to be multiplied by 3.

$$\begin{array}{l}\frac{1}{2}+\frac{5}{6}=\frac{1\times <!--\; \times \; -->3}{2\times <!--\; \times \; -->3}+\frac{5}{2\times <!--\; \times \; -->3}\\ \phantom{\frac{1}{2}+\frac{5}{6}}=\frac{3}{6}+\frac{5}{6}\end{array}$$

You can use prime factorization to find the lcm. First prime factorize each given integer and write products of equal factors as powers, then the lcm will be the product of the highest power of each prime number in the total group of prime factor powers:

$$\begin{array}{rl}\mathrm{factor}<!--\; Function\; Application\; -->\left(540\right)\text{:}& 2^2\times <!--\; \times \; -->3^3\times <!--\; \times \; -->5^{\phantom{1}}\\ \mathrm{factor}<!--\; Function\; Application\; -->\left(1134\right)\text{:}& 2^{\phantom{1}}\times <!--\; \times \; -->3^4\times <!--\; \times \; -->7^{\phantom{1}}\\ \mathrm{lcm}<!--\; Function\; Application\; -->\left(1134,540\right)\text{:}& 2^2\times <!--\; \times \; -->3^4\times <!--\; \times \; -->5^{\phantom{1}}\times <!--\; \times \; -->7^{\phantom{1}}\\ \text{common multiple:}& 2^2\times <!--\; \times \; -->3^4\times <!--\; \times \; -->5^{\phantom{1}}\times <!--\; \times \; -->7^2\\ \text{common multiple:}& 2^3\times <!--\; \times \; -->3^6\times <!--\; \times \; -->5^2\times <!--\; \times \; -->7^3\times <!--\; \times \; -->13\\ \text{common multiple:}& \text{etc.}\end{array}$$

In the example above the "prime factor powers" 2 and 3³ are left over, that is, they are not part of the lcm, since they are not the highest power of a prime number in the total group of prime factor powers. However, 2 × 3³ is the greatest common divisor of 1134 and 540!

This means that multiplying the lcm and gcd yields a product of all prime factor powers, which is the same as multiplying the non-factorized initial integers. This gives us an efficient method to find the lcm through the gcd:

$$\mathrm{lcm}<!--\; Function\; Application\; -->\left(a,b\right)=\frac{a\times <!--\; \times \; -->b}{\gcd <!--\; Function\; Application\; -->\left(a,b\right)}$$

Examples