GCD
What is GCD (Greatest Common Divisor)?
GCD, also known as Greatest Common Factor (GCF), is the largest positive integer that divides two or more numbers without leaving a remainder. It represents the largest number that is a factor of both numbers. The GCD can be found using various methods, with the Euclidean Algorithm being the most efficient.
Key Properties:
1. Always positive
2. GCD(a,b) = GCD(b,a)
3. GCD(a,0) = |a|
4. GCD(a,1) = 1
Methods to Find GCD:
1. Listing Factors Method: Example with 48 and 36:
• Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
• Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
• Common factors: 1, 2, 3, 4, 6, 12 Therefore, GCD(48,36) = 12
2. Euclidean Algorithm:
Formula: GCD(a,b) = GCD(b,r) where r is remainder
Example with 48 and 36:
• 48 = 36(1) + 12
• 36 = 12(3) + 0 Therefore, GCD(48,36) = 12
3. Prime Factorization Method: Example with 48 and 36:
• 48 = 2⁴ × 3
• 36 = 2² × 3²
• Common factors: 2² × 3 Therefore, GCD(48,36) = 12