GCD / GCF Calculator
Calculate the Greatest Common Divisor (GCD), GCF, and HCF for 2 to 10 numbers with interactive Euclidean rectangle tiling blueprint, prime factor Venn diagram, and 4 step-by-step methods.
Largest integer dividing all 2 input numbers evenly with zero remainder.
Explore geometric tiling, factor Venn intersections, and divisor matrices.
Calculation Method Breakdown
Detailed step-by-step mathematical derivation across 4 standard methods.
The Euclidean algorithm repeatedly computes quotients and remainders (a = b × q + r) until remainder = 0. The last non-zero remainder is the GCD.
| Step | Equation (a = b × q + r) | Quotient | Remainder |
|---|---|---|---|
| #1 | 48 = 18 × 2 + 12 | q = 2 | r = 12 |
| #2 | 18 = 12 × 1 + 6 | q = 1 | r = 6 |
| #3 | 12 = 6 × 2 + 0 | q = 2 | r = 0 |
Itemized Calculation Summary
Ready for printing, homework submission, or quick sharing.
======================================== GCD / GCF CALCULATION SUMMARY OctaLone Tools (octalone.com/tools/gcd-calculator) ======================================== Input Numbers: 48, 18 PRIMARY RESULTS: • Greatest Common Divisor (GCD/GCF/HCF): 6 • Least Common Multiple (LCM): 144 PRIME FACTORIZATION BREAKDOWN: • 48 = 2^4 × 3 • 18 = 2 × 3^2 Product Rule Verification: • GCD(48, 18) × LCM(48, 18) = 6 × 144 = 864 • 48 × 18 = 864 (Equal: Yes ✓) ========================================
Did You Know? Euclid's Algorithm Trivia
Oldest Known Algorithm
The Euclidean algorithm, introduced around 300 BCE in Euclid's 'Elements', is widely considered the oldest non-trivial mathematical algorithm still actively used today!
You might also like
Frequently Asked Questions
The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers evenly with a remainder of zero.
The Euclidean algorithm successively divides the larger number by the smaller number (a = b × q + r) and replaces (a, b) with (b, r). This step repeats until the remainder reaches zero. The last non-zero remainder is the GCD.
Write each number as a product of prime powers (e.g. 48 = 2⁴ × 3¹ and 18 = 2¹ × 3²). Find the prime factors that are common to all numbers and select the minimum exponent for each (2¹ and 3¹). Multiply these minimum powers: 2¹ × 3¹ = 6.
If you have a rectangle of dimensions a × b, the Euclidean algorithm can be visualized as cutting the largest possible square tiles from the rectangle. The side length of the smallest square tile that completely fills the remaining rectangle with no gaps or overlap is exactly the GCD.
For any two positive integers a and b, GCD(a, b) × LCM(a, b) = a × b. This means once you find the GCD, the LCM can be computed directly by dividing their product by their GCD: LCM(a, b) = (a × b) ÷ GCD(a, b).
Yes! The calculator supports between 2 and 10 numbers. It utilizes the associative property of the Euclidean algorithm: GCD(a, b, c) = GCD(GCD(a, b), c).
Yes, 100%. The calculator is completely free, private, and works offline via client-side service workers. No calculations or numbers are ever transmitted over the network.