®

Online Calculators

Euclid's Algorithm Calculator

Euclid's Algorithm GCF Calculator


Answer:

GCF(816, 2260) = 4
Greatest Common Factor

Solution
Set up a division problem (a ÷ b = ?) where a is larger than b.

Do the division a ÷ b = c with remainder R.

Then, replace a with b, replace b with R, and do the new division problem.

Continue the process until R = 0.

2260 ÷ 816 = 2 R 628
   (2260 = 2 × 816 + 628)

816 ÷ 628 = 1 R 188
   (816 = 1 × 628 + 188)

628 ÷ 188 = 3 R 64
   (628 = 3 × 188 + 64)

188 ÷ 64 = 2 R 60
   (188 = 2 × 64 + 60)

64 ÷ 60 = 1 R 4
   (64 = 1 × 60 + 4)

60 ÷ 4 = 15 R 0
   (60 = 15 × 4 + 0)

When remainder R = 0, the GCF is the divisor, b, in the last equation. GCF = 4

Calculator Use

Enter two whole numbers to find the greatest common factor (GCF). See the work and learn how to find the GCF using the Euclidean Algorithm.

How to Find the GCF Using Euclid's Algorithm

  1. Given two whole numbers where a is greater than b, do the division a ÷ b = c with remainder R.
  2. Replace a with b, replace b with R and repeat the division.
  3. Repeat step 2 until R=0.
  4. When R=0, the divisor, b, in the last equation is the greatest common factor, GCF.

Since greatest common factor (GCF) and greatest common divisor (GCD) are synonymous, the Euclidean Algorithm process also works to find the GCD.

Related Calculators

To find the GCF of more than two values see our Greatest Common Factor Calculator.

For more information and examples using the Euclidean Algorithm see our GCF Calculator and the section on Euclid's Algorithm.

References

Bureau 42: The Euclidean Algorithm: Greatest Common Factors Through Subtraction.

Rutgers University Department of Mathematics: The Euclidean Algorithm.

 

Cite this content, page or calculator as:

Furey, Edward "Euclid's Algorithm Calculator" at https://www.calculatorsoup.com/calculators/math/gcf-euclids-algorithm.php from CalculatorSoup, https://www.calculatorsoup.com - Online Calculators

Last updated: October 18, 2023

Follow CalculatorSoup: