Greatest Common Divisor Calculator (GCF, HCF, GCD)

Need to simplify fractions or solve ratio problems? Our Greatest Common Divisor (GCD) Calculator finds the highest common factor instantly! Just enter your numbers to reduce fractions, solve Diophantine equations, or simplify ratios

Share Calculator

What is Greatest Common Divisor (GCD)?

In this section, we hope to help us understand what the GCD is, as well as its name, which is the greatest common divisor. Furthermore, it is also called the greatest common factor (GCF) highest common factor (HCF), the greatest common divisor (GCD) greatest common measure (GCM), or the highest common divisor (HCD). A greatest common divisor (sometimes GCD) is the largest integer among all of the integers that all divide them without leaving any remainder. Another name for it is the highest common factor (HCF), or greatest common factor (GCF).

Methods to Calculate GCD

There are three different methods for calculating GCD; these methods are listed below.
1. Prime Factorization Method
2. Division (or Euclidean) Algorithm
3. Binary GCD Algorithm (Stein's Algorithm)
4. Binary Algorithm (Computer's Best Friend)
We will learn three ways here and calculate in three ways.

1. Prime Factorization Method

Here, we will calculate GCD by the prime factorization method.
First, we will find the prime factorization and make a list of the prime factors of each number.
Now, we will identify the common factors and determine the common factors.
We will multiply the common factors to get the GCD.
Let us find the GCD of 48 and 180, for example.
Prime factors of 48:  2⁴ × 3
Prime factors of 180:  2² ×  3² × 5
Common prime factors:  2² and 3
GCD:  2² × 3 = 4 × 3 = 12
So, 48 and 180 GCD are 12 .

Prime Factorization (The Classic Approach)
Steps:
Break numbers into prime factors
Multiply shared primes with lowest exponents
Formula
GCD(a, b) = p₁^{min(α₁, β₁)} × p₂^{min(α₂, β₂)} × ... × pₙ^{min(αₙ, βₙ)}
(Where p = shared primes, α, β = exponents)

2. Euclidean Algorithm

Here we will calculate GCD by the Euclidean algorithm.
Here, we understand the Euclidean algorithm. The Euclidean algorithm is based on the principle that the GCD of two numbers divides their difference as well. We have given below the steps to perform the calculation.
The bigger number will be replaced with the remainder after the greater number has been divided by the smaller number. This procedure will be repeated until the remaining equals zero. The GCD is the non-zero remainder that comes right before this step.
Take an example 1., we will find the GCD of 48 and 180.
180 ÷ 48 = 3 remainder 36
48 ÷ 36 = 1 remainder 12
36 ÷ 12 = 3 remainder 0
So, 48 and 180 GCD are 12

Example 2: GCD of 56 and 98
98 ÷ 56 = 1 remainder42
56 ÷ 42 = 1 remainder 14
42 ÷ 14 = 3 remainder 0 GCD is 14.
So, 56 and 98 GCD are 12

Example 3: GCD of 270 and 192
270 ÷ 192 = 1 remainder 78
192 ÷ 78 = 2 remainder 36
78 ÷ 36 = 2 remainder 6
6 ÷ 6 = 6 remainder 0
GCD = 6.
So, 270 and 192 GCD are 6

3: Division Method (Upside-Down Cake)

[ 12, 18 ]
Divide by 2 → [6, 9]
Divide by 3 → [2, 3] → Stop (no common divisor)
GCD = 2 × 3 = 6

4. Binary Algorithm (Computer's Best Friend)

Identities Used:
GCD(0, a) = a
GCD(a, a) = a
If a and b even: GCD(a,b) = 2 × GCD(a/2, b/2)
If a even, b odd: GCD(a,b) = GCD(a/2, b)
If both odd: GCD(a,b) = GCD(|a-b|, min(a,b))

GCD Calculation Examples: Step-by-Step

Example 1: GCD of 48 and 60 (Prime Factorization)

48 = 2⁴ × 3¹
60 = 2² × 3¹ × 5¹
Shared primes: 2^{min (4,2)} × 3^{min (1,1)} = 2² × 3 = 12

Example 2: GCD of 1071 and 462 (Euclidean Algorithm)

1071 ÷ 462 = 2 remainder 147
462 ÷ 147 = 3 remainder 21
147 ÷ 21 = 7 remainder 0 → GCD = \boxed{21}

Example 3: GCD of 81 and 54 (Division Method)

[81, 54] ÷ 3 → [27, 18]
[27, 18] ÷ 3 → [9, 6]
[9, 6] ÷ 3 → [3, 2] → Stop
GCD = 3 × 3 × 3 = \boxed{27}

Tiling: Where GCD Rules Your Real Life!

You have a rectangular room 24m × 18m. What's the largest square tile that can cover it without cutting?
GCD Solution:
Find GCD 24 and 18 = 6
Largest possible tile = 6m × 6m
Verification:
Rows: 24 ÷ 6 = 4 tiles
Columns: 18 ÷ 6 = 3 tiles
Total tiles: 4 × 3 = 12 (perfect fit!)

FAQs

Q 1. What is the GCD of 12, 18, 24, and 36?
The GCD is 6. Here's why: All are divisible by 6 (12/6 = 2, 18/6 = 3, 24/6 = 4, 36/6 = 6), and nothing larger works for all. Use a calculator or Euclidean pairwise to

Q 2. How do I calculate the GCD of 48 and 36 with the upside-down method?
The upside-down method (or ladder/cake method) goes like this:
Write 48 and 36 side by side.
Divide both by 2: 24 and 18. Write 2 on the left.
Divide by 2 again: 12 and 9. Another 2.
Divide by 3: 4 and 3. Write 3.
No more common factors. GCD = 2 × 2 × 3 = 12.
Visualize it like an L-shape ladder—super easy!

Q 3. What identities power the binary GCD algorithm?
The binary algorithm uses these 5 superpowers:
Base Case: GCD(0, a) = a
Reflexivity: GCD(a, a) = a
Even-Even Rule: GCD(2a,2b) = 2 × GCD(a,b)
Even-Odd Rule: GCD(2a,b) = GCD(a,b) if b odd
Odd-Odd Rule: GCD(a,b) = GCD(|a-b|, min(a,b)) if a,b odd

References

For more information Greatest Common Divisor.