Euclid's Algorithm GCF Calculator

Enter Calculation

Value 1

Value 2

Results

https://example.com

Greatest Common Factor

4

GCF (also called GCD)

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

What is Euclid's Algorithm?

The greatest common factor (GCF), also called the greatest common divisor (GCD), is the largest whole number that divides two integers exactly. Euclid's Algorithm is an ancient, remarkably efficient method for finding it using repeated division with remainder. This calculator returns the GCF of any two whole numbers and shows every division step so you can follow the work.

Euclid's algorithm tiles a rectangle with the largest possible equal squares — that square's side is the GCF.

How to use it

Enter two whole numbers in Value 1 and Value 2. The tool takes the larger as the dividend and the smaller as the divisor, then divides repeatedly until the remainder is zero. The last nonzero divisor is the GCF. Order does not matter and negative signs are ignored, since the GCF depends only on magnitude.

The formula explained

At each step you compute a quotient and a remainder: \(a = c \times b + R\), where \(c = \lfloor a / b \rfloor\) and \(R = a \bmod b\). You then replace a with b and b with R and repeat. Because each remainder is strictly smaller than the previous divisor, the process always terminates. When \(R = 0\), the current divisor is the answer. As a recursion:

$$\gcd(a, b) = \gcd(b, a \bmod b),\quad \gcd(a, 0) = a$$

Advertisement

Worked example

Find GCF(816, 2260). Set \(a = 2260\), \(b = 816\).

$$2260 = 2 \times 816 + 628$$$$816 = 1 \times 628 + 188$$$$628 = 3 \times 188 + 64$$$$188 = 2 \times 64 + 60$$$$64 = 1 \times 60 + 4$$$$60 = 15 \times 4 + 0$$

The remainder hits zero with divisor 4, so GCF(816, 2260) = 4.

Each step replaces (a, b) with (b, a mod b) until the remainder is 0; the last nonzero divisor is the GCF.

FAQ

Are GCF and GCD the same thing? Yes. "Greatest common factor" and "greatest common divisor" are synonyms; this tool answers both.

What if one input is 0? \(\gcd(a, 0) = a\), because every number divides 0. If both are 0, the GCF is undefined.

Can I find the GCF of three numbers? Apply the tool pairwise: \(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\).