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.

30 45 = 2×3×5 3×3×5 = 2 3

gcd 30,45 = 3 × 5 = 15

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, 6 35 is in lowest terms:

gcd 6,35 = 1

6 35 = 2×3 5×7 = 6 35

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.

gcd 13,0 = 13

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:

gcd(930,54) = 6
1 7
54 ) 9 3 0
5 4
3 9 0
3 7 8 4
1 2 ) 5 4
4 8 2
6 ) 1 2
1 2
0
930/54=17r12
54/12=4r6
12/6=2r0
gcd(84,60) = 12
1
60 ) 8 4
6 0 2
2 4 ) 6 0
4 8 2
1 2 ) 2 4
2 4
0
84/60=1r24
60/24=2r12
24/12=2r0

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

54 930 = 6×9 6×155 = 9 155

60 84 = 12×5 12×7 = 5 7

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

gcd(a,b), 0 ≤ a,b < 100 000.

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.

1 2 + 5 6 = 6 12 + 10 12 = 16 12 16 12 = 4×4 4×3 = 4 3 = 1 1 3

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.

lcm 2,6 = 6

1 2 + 5 6 = 3 6 + 5 6 = 8 6 = 4 3

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.

1 2 + 5 6 = 1×3 2×3 + 5 2×3 1 2 + 5 6 = 3 6 + 5 6

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:

factor 540 : 22 × 33 × 51 factor 1134 : 21 × 34 × 71 lcm 1134 540 : 22 × 34 × 51 × 71 common multiple: 22 × 34 × 51 × 72 common multiple: 23 × 36 × 52 × 73 × 13 common multiple: etc.

In the example above the "prime factor powers" 2 and 33 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 × 33 is the greatest common divisor of 1134 and 540!

540 1134 = 2 × 33 2 × 33 × 2 × 5 3 × 7

gcd 1134 540 = 2 × 33

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:

lcm a b = a×b gcd a b

Examples

Example 1:

2 15 1 18 =

gcd(15,18) = 3 because:

1
15 ) 1 8
1 5 5
3 ) 1 5
1 5
0

lcm 15 18 = 15×18 3 lcm 15 18 = 5×18 = 15×6 = 90

2 15 1 18 = 2 × 6 15 × 6 5 5 × 18 = 7 90


Example 2:

2 102 + 2 78 =

gcd(102,78) = 6 because:

1
78 ) 1 0 2
7 8 3
2 4 ) 7 8
7 2 4
6 ) 2 4
2 4
0

lcm 102 78 = 102×78 6 lcm 102 78 = 17×78 = 102×13

2 102 + 2 78 = 2 × 13 102 × 13 + 2 × 17 78 × 17 2 102 + 2 78 = 60 78 × 17 2 102 + 2 78 = 2 × 2 × 3 × 5 2 × 3 × 13 × 17 2 102 + 2 78 = 2 × 5 13 × 17 = 10 221


The answer 60/1326 is reduced to 10/221 by using factorization of the numerator and denominator. Now try to reduce 60/1326 by using the gcd.


Example 3:

1 6 + 1 10 + 1 12 =


lcm 6 10 = 6×10 2 lcm 6 10 = 3×10 = 6×5 = 30

1 6 + 1 10 = 5 5 × 6 + 3 3 × 10 = 8 30


1 6 + 1 10 + 1 12 = 8 30 + 1 12

gcd(30,12) = 6 because:

2
12 ) 3 0
2 4 2
6 ) 1 2
1 2
0

lcm 30 12 = 30×12 6 lcm 30 12 = 30×2 = 5×12 = 60

8 30 + 1 12 = 8 × 2 30 × 2 + 5 5 × 12 8 30 + 1 12 = 21 30 × 2 = 7 10 × 2


1 6 + 1 10 + 1 12 = 7 20


Example 4:

Order the next fractions from least to greatest: 4 9 3 4 4 5 11 12 13 15

Answer:

4 32 3 22 4 5 11 22×3 13 3×5 lcm 9 4 5 12 15 = 22×32×5 The given sequence of fractions now written with a common denominator: 4×22×5 22×32×5 3×32×5 22×32×5 4×22×32 22×32×5 11×3×5 22×32×5 13×22×3 22×32×5 80 22×32×5 135 22×32×5 144 22×32×5 165 22×32×5 156 22×32×5 Thus: 4 9 < 3 4 < 4 5 < 13 15 < 11 12