Greatest Common Divisor & Least Common Multiple

Chapter

1 video

INTRODUCTION

The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) are important concepts in number theory. The GCD and LCM allow for finding numerical connections between several natural numbers and are key in factoring numbers and working with fractions.

GREATEST COMMON DIVISOR (GCD)

The Greatest Common Divisor of two or more numbers is the largest number that divides all the given numbers without a remainder. It is denoted as GCD(a, b) (or sometimes HCF for Highest Common Factor).

Example: For the numbers 24 and 36, let's find all divisors:

• Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
• Divisors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36 The Greatest Common Divisor is GCD(24, 36) = 12.

METHODS FOR FINDING GCD

1. PRIME FACTORIZATION METHOD:
2. 24 = 2³ × 336 = 2² × 3²Common factors (take the lowest power of common prime factors): 2² × 3¹ = 4 × 3 = 12.
3. EUCLIDEAN ALGORITHM (for two numbers a and b, where a > b): GCD(a, b) = GCD(b, remainder of a ÷ b) Repeat the process until the remainder is 0. The last non-zero remainder is the GCD.

LEAST COMMON MULTIPLE (LCM)

The Least Common Multiple of two or more numbers is the smallest number that is a multiple of all the given numbers. It is denoted as LCM(a, b).

Example: For the numbers 4 and 6, let's find their multiples:

• Multiples of 4: 4, 8, 12, 16, 20, 24, …
• Multiples of 6: 6, 12, 18, 24, 30, … The Least Common Multiple is LCM(4, 6) = 12.

METHODS FOR FINDING LCM

1. PRIME FACTORIZATION METHOD:
2. 4 = 2²6 = 2 × 3Take all prime factors from both numbers, using the highest power of each factor that appears: 2² × 3 = 4 × 3 = 12.
3. FORMULA USING GCD: LCM(a, b) = (|a × b|) / GCD(a, b) For LCM(24, 36): LCM(24, 36) = (24 × 36) / 12 = 864 / 12 = 72.

RELATIONSHIP BETWEEN GCD AND LCM

The Greatest Common Divisor and the Least Common Multiple are related by the equation:

GCD(a, b) × LCM(a, b) = |a × b| This means that the product of the GCD and LCM of two numbers is always equal to the absolute value of the product of those two numbers.

CONCLUSION

The Greatest Common Divisor and the Least Common Multiple are key concepts in number theory that allow for the simplification of arithmetic operations. The GCD helps in finding common factors, while the LCM helps in determining common multiples.

GCD and LCM – Exercise

Explanation