Understanding GCD / HCF Calculator
The Greatest Common Divisor (GCD), also called Highest Common Factor (HCF) or Greatest Common Factor (GCF), is the largest positive integer that divides two or more given integers without leaving a remainder.
GCD(48, 18) = 6
Because 6 is the largest number that divides both 48 and 18 evenly.
48 รท 6 = 8 โ 18 รท 6 = 3 โ
Euclidean Algorithm โ Step by Step
The most efficient algorithm for finding GCD is the Euclidean algorithm, dating back to 300 BC. It works by repeatedly applying division with remainder.
GCD(a, b) = GCD(b, a mod b) until remainder = 0
Example: GCD(252, 105)
- 252 = 105 ร 2 + 42 โ GCD(252, 105) = GCD(105, 42)
- 105 = 42 ร 2 + 21 โ GCD(105, 42) = GCD(42, 21)
- 42 = 21 ร 2 + 0 โ GCD(42, 21) = 21 โ
GCD(252, 105) = 21
Prime Factorization Method
An alternative: find prime factorizations of both numbers, then multiply the common prime factors.
Example: GCD(360, 48)
360 = 2ยณ ร 3ยฒ ร 5
48 = 2โด ร 3
Common factors: 2ยณ ร 3ยน = 8 ร 3 = 24
48 = 2โด ร 3
Common factors: 2ยณ ร 3ยน = 8 ร 3 = 24
Applications of GCD
- Simplifying fractions: 18/24 โ GCD(18,24)=6 โ 3/4
- Tiling problems: Largest square tile that fits a 48ร18 floor = GCD(48,18) = 6 ft tiles
- Scheduling: Two buses with periods 48 and 18 minutes will coincide every LCM minutes. GCD is needed to find LCM.
- Cryptography: RSA encryption uses GCD in key generation
- Computer science: Modular arithmetic, Bezout's theorem, Diophantine equations