Euclid's Algorithm Calculator

Find the GCF/GCD of two numbers using Euclid's Algorithm with step-by-step work.

Find GCD using Euclid's Algorithm with step-by-step division. Also calculates LCM using the GCD × LCM = a × b relationship.

Enter two positive integers
GCD
?
Max 1 billion per number
Try:
help_outlineHow to Useexpand_more

Finding the GCD Using Euclid's Algorithm

This calculator finds the Greatest Common Factor (GCF) of two whole numbers using the Euclidean Algorithm. Enter any two positive integers to see the complete step-by-step solution showing how the algorithm works.

How the Euclidean Algorithm Works:

  1. Divide: Given two numbers where a > b, perform a ÷ b = c with remainder R
  2. Replace: Replace a with b, and replace b with remainder R
  3. Repeat: Continue the division process with the new values
  4. Stop: When R = 0, the divisor b in the last equation is the GCD

GCF vs GCD:

Greatest Common Factor (GCF) and Greatest Common Divisor (GCD) are synonymous terms. The Euclidean Algorithm works to find both. Some regions also call this the Highest Common Factor (HCF).

infoWhat is Euclid's Algorithm Calculator?expand_more

Euclid's Algorithm (also called the Euclidean Algorithm) is an efficient method for computing the Greatest Common Divisor (GCD) of two integers. Dating back to ancient Greece around 300 BCE, it is one of the oldest algorithms still in common use today.

The algorithm is based on the principle that the GCD of two numbers also divides their difference. By repeatedly applying division and taking remainders, the numbers are reduced until one becomes zero—at which point the other number is the GCD.

Why use Euclid's Algorithm? It's remarkably efficient, especially for large numbers. While listing all factors becomes impractical for large integers, the Euclidean Algorithm can find the GCD in relatively few steps regardless of the number size.

functionsFormulaexpand_more

Euclid's Algorithm Formula:

GCD(a, b) = GCD(b, a mod b)

Repeat until remainder = 0

The last non-zero remainder is the GCD

Step-by-Step Process:

1. If a < b, swap them so a ≥ b

2. Divide: a ÷ b = quotient with remainder R

3. Set: a = b, b = R

4. If R ≠ 0, go back to step 2

5. If R = 0, then GCD = b (the divisor)

GCD and LCM Relationship:

GCD(a, b) × LCM(a, b) = a × b

Once you know the GCD, calculate LCM easily

lightbulbExamplesexpand_more

Example 1: GCD(48, 18)

Step 1: 48 = 2 × 18 + 12

Step 2: 18 = 1 × 12 + 6

Step 3: 12 = 2 × 6 + 0

Remainder is 0 → GCD = 6

Example 2: GCD(252, 105)

Step 1: 252 = 2 × 105 + 42

Step 2: 105 = 2 × 42 + 21

Step 3: 42 = 2 × 21 + 0

Remainder is 0 → GCD = 21

Example 3: GCD(1071, 462)

Step 1: 1071 = 2 × 462 + 147

Step 2: 462 = 3 × 147 + 21

Step 3: 147 = 7 × 21 + 0

Remainder is 0 → GCD = 21

Example 4: GCD(17, 13) - Coprime Numbers

Step 1: 17 = 1 × 13 + 4

Step 2: 13 = 3 × 4 + 1

Step 3: 4 = 4 × 1 + 0

Remainder is 0 → GCD = 1 (coprime)

quizFAQexpand_more
Why is Euclid's Algorithm so efficient?expand_more
The algorithm reduces the numbers significantly with each step. The number of steps is proportional to the number of digits, not the size of the numbers themselves. This makes it vastly faster than listing all factors, especially for large numbers.
What is the relationship between GCD and LCM?expand_more
For any two numbers a and b: GCD(a,b) × LCM(a,b) = a × b. This means once you find the GCD using Euclid's Algorithm, you can easily calculate the LCM by dividing the product by the GCD.
Can Euclid's Algorithm work with more than two numbers?expand_more
Yes. Find the GCD of the first two numbers, then find the GCD of that result with the third number, and continue. Mathematically: GCD(a, b, c) = GCD(GCD(a, b), c).
What if the two numbers are coprime?expand_more
If two numbers are coprime (relatively prime), Euclid's Algorithm will eventually reach a remainder of 1, then 0. The GCD of coprime numbers is always 1. For example, GCD(17, 13) = 1.
How old is Euclid's Algorithm?expand_more
Euclid's Algorithm dates back to around 300 BCE, appearing in Euclid's Elements. It is one of the oldest algorithms still in widespread use today, demonstrating its elegance and efficiency.