GCD and LCM – Exercise

DEFINITION OF THE GREATEST COMMON DIVISOR (GCD)

The Greatest Common Divisor (GCD) of two or more integers is the largest integer that divides all of them without leaving a remainder.

DEFINITION OF THE LEAST COMMON MULTIPLE (LCM)

The Least Common Multiple (LCM) of two or more integers is the smallest positive integer that is divisible by all of these numbers.

METHODS FOR CALCULATING GCD AND LCM

Several methods exist for calculating the Greatest Common Divisor and the Least Common Multiple. Among them, the most well-known are:

• The Euclidean algorithm for the Greatest Common Divisor.
• Using prime factorization for both GCD and LCM.
• Using the fundamental rule that the Least Common Multiple is equal to the product of the numbers divided by their Greatest Common Divisor: LCM(a, b) = (|a × b|) / GCD(a, b).

EXAMPLE PROBLEM

Let's calculate the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) for the numbers 18 and 12.

GREATEST COMMON DIVISOR (GCD):

First, we find the prime factorization of the numbers:

• 18 = 2 × 3²
• 12 = 2² × 3

The common prime factors are 2 and 3.
The Greatest Common Divisor is the product of the lowest powers of these common prime factors:
GCD(18, 12) = 2¹ × 3¹ = 2 × 3 = 6.

LEAST COMMON MULTIPLE (LCM):

Method 1: Using the product and GCD
First, calculate the product of the numbers: 18 × 12 = 216.
Then, calculate the LCM as the product of the numbers divided by their GCD:
LCM(18, 12) = 216 / 6 = 36.

Method 2: Using prime factorization
The Least Common Multiple is the product of the highest powers of all prime factors present in either number:
Prime factors involved are 2 and 3.
Highest power of 2 is 2² (from 12).
Highest power of 3 is 3² (from 18).
LCM(18, 12) = 2² × 3² = 4 × 9 = 36.