Greatest Common Divisor and Least Common Multiple

Both greatest common divisor and least common multiple are essential and extremely important operations in mathematics, without them mathematical operations would be quite a tedious task and possibly more complicated to do, the reason is that both operations are used in the simplification of fractions and the calculation of common numbers with respect to a larger group of numbers.

Prime Numbers

It is important to refer to prime numbers, and the reason is that they are going to be used for operations in both the calculation of the greatest common divisor and the least common multiple, since it presents certain operational advantages over other methods, it is important to note that prime numbers is a specific sequence of numbers, Starting from 2 to infinity, a prime number is a number that divides only by itself and by unity(1). The first prime numbers between EL and 100 are shown in the table in the initial image of this article, highlighted in red. 2, 3, 5, 7, 11, 13,17…

Greatest Common Divisor

From a group of numbers, the greatest common divisor is a specific number of the highest possible value that has the particularity of being able to divide all the numbers in that group. There can be several ways to get the greatest common divisor of a group of numbers, however, it is conducive to using the prime number method, as you can use pretty much the same method with the minimum with a multiple, which makes it convenient in the long run. And also in some way, to refer to the fundamental theorem of arithmetic, it states that any number can be expressed as the multiplication of prime factors, which guarantees the effectiveness of the method of prime numbers.

To be able to apply the method of prime numbers it is necessary to know how to decompose the number as a multiplication of prime factors, basically what we are doing is simply applying the theorem of arithmetic through successive divisions and using the sequence of prime numbers (2,3,5,7,11,13,…) as divisors each time we make the successive divisions, for example:

Decompose the number 8316 into prime factors:

8316 | 2
4158 | 2
2079 | 3
 693 | 3
 231 | 3
  77 | 7
  11 | 11
   1

8316 = 2*2*3*3*3*7*11 = 2² * 3³ * 11

8316 = 2² * 3³ * 11

With the above in mind, we can proceed to obtain the greatest common divisor of any group of numbers:

Example 2: Getting the Greatest Common Divisor of 60 and 160

Clearly, each number must be broken down into its separate prime factors:

60 | 2 30 | 2 15 | 3 5 | 5 1 60 = 2² * 3 * 5

160 | 2 80 | 2 40 | 2 20 | 2 10 | 2 5 | 5 1 160 = 2⁵ * 5

Having the numbers decomposed, we proceed to obtain the greatest common divisor (GCD), it is composed of the common factors with their smallest exponent, both 2 and 5 are present in the two numbers and the smallest exponent is 2², then:

GCD(60,160) = 2²*5 = 4 * 5=20

GCD(60,160) = 20

Least Common Multiple

Keeping in mind the prime numbers and the successive divisions by means of prime numbers, the least common multiple (LCM) is an operation whose result is the decomposition of each number into prime factors, so that the LCM is the multiplication of common and non-common factors with their greatest exponent.

Example: Get the least common multiple of 210, 360, 548

210 | 2 105 | 3 35 | 5 7 | 7 1 210 = 2*3*5*7

360|2 180|2 90|2 45|3 15|3 5|5 1 360 = 2³ * 3² * 5

548 | 2 274 | 2 137 | 137 1 548 = 2² * 3 * 137

Taking the numbers in their common factors, we obtain the mcm of 210, 360, 548, keeping in mind that it is the multiplication of common and non-common factors with its greatest exponent:

LCM(210,360,548) = 2³ * 3² * 5 * 7 *137 = 345240

LCM(210,360,548) = 345240

Clearly, an article with exercises is necessary, but that will be for the next one.