The greatest common divisor (GCD), also known as the greatest common factor (GCF), is
the largest positive integer that divides two or more numbers without leaving a remainder.
It’s useful for simplifying fractions, finding common factors, and solving various
mathematical problems.
How to Find the GCD
1. Listing Factors:
o List all the factors of each number and find the largest one they share.
o Example: For 8 and 12:
▪ Factors of 8: 1, 2, 4, 8
▪ Factors of 12: 1, 2, 3, 4, 6, 12
▪ GCD is 4.
2. Prime Factorization:
o Break each number into its prime factors.
o Example: For 18 (2 × 3²) and 24 (2³ × 3):
▪ Common prime factors: 2¹ (smallest power of 2) and 3¹ (smallest
power of 3).
▪ GCD = 2¹ × 3¹ = 6.
3. Using the Euclidean Algorithm:
o A more efficient method, especially for larger numbers:
▪ Divide the larger number by the smaller one and find the remainder.
▪ Replace the larger number with the smaller number and the smaller
number with the remainder.
▪ Repeat until the remainder is 0. The last non-zero remainder is the
GCD.
o Example: For 48 and 18:
▪ 48 ÷ 18 = 2 (remainder 12)
▪ 18 ÷ 12 = 1 (remainder 6)
▪ 12 ÷ 6 = 2 (remainder 0)
▪ GCD is 6.
Applications of GCD
• Simplifying Fractions: To reduce fractions to their simplest form.
• Finding Common Factors: Useful in number theory and algebra.
• Problem Solving: In problems involving divisibility and number relationships.
Example
Find the GCD of 36 and 60:
1. Listing Factors:
o Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
o Factors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
o GCD is 12.
2. Prime Factorization:
o 36 = 2² × 3²
o 60 = 2² × 3¹ × 5¹
o GCD = 2² × 3¹ = 12.
3. Using the Euclidean Algorithm:
o 60 ÷ 36 = 1 (remainder 24)
o 36 ÷ 24 = 1 (remainder 12)
o 24 ÷ 12 = 2 (remainder 0)
o GCD is 12.
Understanding the GCD helps in many mathematical applications and problem-solving
scenarios!
