# Why does the number 216 matter

The least common multiple and the greatest common divisor of two numbers are two important and useful objects in arithmetic. Their definitions are basically already in their names: The greatest common divisor (\ (\ textrm {gcd} \)) of two natural numbers is defined as the greatest number that divides both one and the other number; the least common multiple (\ (\ textrm {kgV} \)) of two natural numbers is accordingly the smallest number that is both a multiple of one and a multiple of the other.

For example 6 is the \ (\ textrm {gcd} \) of \ (24 \) and \ (30 \), while \ (120 \) is the \ (\ textrm {kgV} \) of these numbers. The \ (\ textrm {ggT} \) of \ (5 \) and \ (100 \) is \ (5 \), their \ (\ textrm {kgV} \) is \ (100 \). Numbers whose \ (\ textrm {gcd} 1 \) are called coprime. Two different prime numbers are always prime, but \ (15 \) and \ (28 \) are also prime numbers. There is an important connection between the \ (\ textrm {kgV} \) and the \ (\ textrm {ggT} \): the product of \ (\ textrm {ggT} \) and the \ (\ textrm {kgV} \ ) two numbers is always equal to the product of the numbers themselves; in the above example we had \ (6 \) or \ (120 \) as \ (\ textrm {ggT} \) or \ (\ textrm {kgV} \) of the numbers \ (24 \) and \ (30 \) ) and actually \ (6 \ times 120 = 720 = 24 \ times 30 \).

There are different ways to calculate the \ (\ textrm {ggT} \) and the \ (\ textrm {kgV} \) of two numbers, three of which are presented here:

Divisor or multiple comparison

This method is the easiest to understand, but also (for large numbers) the one with the highest computational effort. For the \ (\ textrm {ggT} \) one simply creates a list of the divisors for both numbers. Then you compare these lists and look for the largest number that appears in both lists. For \ (24 \) the factors \ (1 \), \ (2 \), \ (3 \), \ (4 \), \ (6 \), \ (8 \), \ (12 \) , \ (24 \). For \ (30 \) one has the factors \ (1 \), \ (2 \), \ (3 \), \ (5 \), \ (6 \), \ (10 ​​\), \ (15 \) ), \ (30 \). Since \ (6 \) is the largest number that appears in both lists, \ (6 \) is the \ (\ textrm {gcd} \) of \ (24 \) and \ (30 \). With the \ (\ textrm {kgV} \) one proceeds in the same way: For both numbers one creates a list with multiples (since the list would actually be infinitely long, one stops at the product of the two numbers - the \ (\ (\ textrm {kgV} \) yes not be), and then compares the lists. The smallest number that appears in both lists is then the \ (\ textrm {kgV} \) of these numbers.
The multiples of \ (24 \) are:

\(24\), \( 48\), \( 72\), \( 96\), \( 120\), \( 144\), \( 168\), \( 192\), \( 216\), \( 240\), \( 264\), \( 288\), \( 312\), \( 336\), \( 360\), \( 384\), \( 408\), \( 432\), \( 456\), \( 480\), \( 504\), \( 528\), \( 552\), \( 576\), \( 600\), \( 624\), \( 648\), \( 672\), \( 696\), \( 720\),...

The multiples of \ (30 \) are:

\(30\), \(60\), \(90\), \(120\), \(150\), \(180\), \(210\), \(240\), \(270\), \(300\), \(330\), \( 360\), \( 390\), \( 420\), \( 450\), \( 480\), \( 510\), \( 540\), \( 570\), \( 600\), \( 630 \), \(660\), \( 690\), \( 720\),...

The smallest number on both lists is \ (120 \), that means \ (\ textrm {kgV} \) of \ (30 \) and \ (24 \) is \ (120 \).

Another method to determine \ (\ textrm {ggT} \) and \ (\ textrm {kgV} \) is the

Comparison of the prime factorization:

In this method, the prime factorization of the two numbers is compared: one first writes the prime factorization of the two numbers on top of each other. Then one searches for the \ (\ textrm {gcd} \) for those prime numbers that occur in both decompositions. Then consider the smaller exponent for each of these prime numbers. The product of these prime numbers to the power of the respective smaller exponent is then the \ (\ textrm {gcd} \) of these numbers. Example:
\ (24 = 2 ^ 3 \ times 3 ^ 1 30 = 2 ^ 1 \ times 3 ^ 1 \ times 5 ^ 1 \)
the common prime factors are: \ (2 \) (smallest exponent \ (1 \)), \ (3 \) (smallest exponent \ (1 \)). That means, \ begin {align *} \ textrm {ggT} (24.30) = 2 ^ 1 \ cdot 3 ^ 1 = 6. \ End {align *}
For the \ (\ textrm {kgV} \) we first consider all occurring prime factors and the largest exponent for these prime factors. The product of these prime numbers to the power of the larger exponent is then the \ (\ textrm {kgV} \). Example:
\ (24 = 2 ^ 3 \ times 3 ^ 1 30 = 2 ^ 1 \ times 3 ^ 1 \ times 5 ^ 1 \)
all occurring prime factors are: \ (2 \) (largest exponent \ (3 \)), \ (3 \) (largest exponent \ (1 \)), \ (5 \) (largest exponent \ (1 \)). That means \ begin {align *} \ textrm {kgV} (24.30) = 2 ^ 3 \ times 3 ^ 1 \ times 5 ^ 1 = 8 \ times 3 \ times 5 = 120. \ End {align *}
As you learned in the Prime Numbers chapter, prime factorization for large numbers is not always easy. For the determination of the \ (\ textrm {gcd} \) one often uses more efficient methods, the best known is the so-called. Euclidean algorithm

Euclidean Algorithm

The Euclidean algorithm is an extremely efficient method for the determination of the \ (\ textrm {gcd} \). You use it when you want to calculate the \ (\ textrm {gcd} \) of particularly large numbers. Amazingly, it is already over 2000 years old!
First you divide the smaller number by the larger number (with remainder). Then you divide the remainder by the smaller number and get a new remainder. Continue this way until the remainder is zero at some point. The \ (\ textrm {ggT} \) of the two numbers is then the last number that has been divided by. The (comparatively large) numbers \ (17262 \) and \ (8580 \) should serve as an example. We expect:
\ begin {align *}
17262 \ div 8580 & = 2 \ \ textrm {rest} \ 102 \
8580 \ div 102 & = 84 \ \ textrm {rest} \ 12 \
102 \ div12 & = 8 \ \ textrm {remainder} \ 6 \
12 \ div 6 & = 2 \ \ textrm {remainder} \ 0 \
\ end {align *}

This means that the \ (\ textrm {ggT} \) of \ (17262 \) and \ (8580 \) is \ (6 \).
There is no comparable method for determining the \ (\ textrm {kgV} \), but because of the formula \ (\ textrm {ggT} (a, b) \ cdot \ textrm {kgV} (a, b) = a \ cdot b \) the \ (\ textrm {kgV} \) can still be calculated from \ (17262 \) and \ (8580 \), one has:
\ begin {align *} \ textrm {kgV} (17262.8580) = 17262 \ cdot 8580 \ div \ textrm {ggT} (17626.8580) = 24684660. \ end {align *}