Euclidean Algorithm Calculator

Enter two whole numbers to find their GCF with every division step shown.

Examples:1,071, 462252, 10548, 18270, 192

The GCF of 1,071 and 462 is 21.

Division steps (3)

  1. Step 1: 1,071 = 2 × 462 + 147
  2. Step 2: 462 = 3 × 147 + 21
  3. Step 3: 147 = 7 × 21 + 0

The remainder reaches 0, so the last non-zero remainder, 21, is the GCF.

Related results

LCM(1,071, 462) = 23,562

1,071 and 462 are not coprime, because they share the factor 21.

What Is the Euclidean Algorithm?

The Euclidean algorithm finds the greatest common factor of two numbers using only division with remainder. It is one of the oldest algorithms still in use, and it works on huge numbers without any factoring.

How to Use This Euclidean Algorithm Calculator

  1. Type two whole numbers into the boxes.
  2. Press Calculate to see every division step, the GCF and the LCM.

How the Euclidean Algorithm Works

  1. Divide the larger number by the smaller one and note the remainder.
  2. Replace the larger number with the smaller, and the smaller with the remainder.
  3. Repeat until the remainder is 0.
  4. The last non-zero remainder is the GCF.
Handwritten notebook page running the Euclidean algorithm on 1071 and 462 to get a GCF of 21
1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0. The GCF is 21.

Why It Works

Any number that divides both a and b also divides the remainder of a ÷ b. So the pair (a, b) has the same GCF as the smaller pair (b, remainder). The numbers shrink each step until the remainder reaches 0.

From the GCF to the LCM

Once you have the GCF, the LCM is the product of the two numbers divided by the GCF. For 252 and 105 the GCF is 21, so the LCM is 252 × 105 ÷ 21 = 1,260.

Handwritten notebook page running the Euclidean algorithm on 252 and 105 to get a GCF of 21
252 = 2 × 105 + 42, 105 = 2 × 42 + 21, 42 = 2 × 21 + 0. The GCF is 21.

Worked Examples

Common mistakes

Euclidean Algorithm Calculator FAQs

What is the Euclidean algorithm?

It is a fast way to find the greatest common factor of two numbers using repeated division with remainder. The last non-zero remainder is the GCF.

How do you use the Euclidean algorithm?

Divide the larger number by the smaller one and keep the remainder. Divide the smaller number by that remainder, and repeat until the remainder is 0. The last non-zero remainder is the GCF.

What is the GCF of 1071 and 462?

The GCF is 21. 1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, and 147 = 7 × 21 + 0.

Why does the Euclidean algorithm work?

Any number that divides both a and b also divides the remainder of a ÷ b. So the pair (a, b) has the same GCF as the smaller pair (b, remainder), and the numbers shrink until the remainder is 0.

Is the Euclidean algorithm faster than prime factorization?

For large numbers, yes. It never needs to factor anything, and it finishes in a small number of division steps.

What does it mean if the GCF is 1?

The two numbers are coprime. They share no prime factor, and their LCM is simply their product.

How do you find the LCM from the Euclidean algorithm?

Divide the product of the two numbers by their GCF. For 252 and 105 the GCF is 21, so the LCM is 252 × 105 ÷ 21 = 1,260.

Does the order of the two numbers matter?

No. If you enter the smaller number first, the first step simply swaps them.

More Worked Examples

Showing 4 of 4 examples