VerifySolveSolve a problem

GCD Calculator — Euclid's way, proven twice

Type two or more numbers and get the GCD by Euclid's algorithm — every remainder shown — cross-checked by prime factorization, with the LCM as the mirror result. Then this gcd calculator proves both routes agree.

  • ✓100% free — no paywall, ever
  • ✓No sign-up, no app
  • ✓Every answer verified before you see it

In short

The greatest common divisor is the largest number dividing every input. Euclid's algorithm finds it by repeated division with remainder — the last non-zero remainder is the GCD — and prime factorization confirms it by taking the lowest power of each prime. This gcd calculator shows both routes, with the LCM alongside, and proves they agree.

Euclid's algorithm, in four lines

One method handles every GCD problem: divide, keep the remainder, repeat. This gcd calculator names each move so the method transfers to your homework.

One Euclid step

180=48×3+36180 = 48 \times 3 + 36

Lowest powers (GCD)

gcd⁡(48,180)=22×3=12\gcd(48, 180) = 2^2 \times 3 = 12

Highest powers (LCM)

lcm(48,180)=24×32×5=720\mathrm{lcm}(48, 180) = 2^4 \times 3^2 \times 5 = 720

The two-number identity

gcd⁡(a,b)×lcm(a,b)=a×b\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b

Worked examples — Euclid, checked twice

A pair, a triple, and coprime numbers. Every check below is the same verification this gcd calculator prints on every problem.

GCD(48, 180)

  1. 1.180 = 48 × 3 + 36
  2. 2.48 = 36 × 1 + 12
  3. 3.36 = 12 × 3 + 0

GCD = 12, LCM = 720

Cross-check: 48 = 2⁴ × 3, 180 = 2² × 3² × 5 — lowest powers 2² × 3 = 12 ✓.

GCD(17, 23)

  1. 1.23 = 17 × 1 + 6
  2. 2.17 = 6 × 2 + 5
  3. 3.6 = 5 × 1 + 1
  4. 4.5 = 1 × 5 + 0

GCD = 1, LCM = 391

Coprime: no shared prime factors, so the GCD is 1 and the LCM is the product ✓.

GCD(12, 18, 30)

  1. 1.GCD(12, 18) = 6 by Euclid
  2. 2.GCD(6, 30) = 6 by Euclid

GCD = 6, LCM = 180

Cross-check: lowest powers 2 × 3 = 6 ✓; 180 ÷ 12, 18 and 30 all divide evenly ✓.

GCD(100, 75)

  1. 1.100 = 75 × 1 + 25
  2. 2.75 = 25 × 3 + 0

GCD = 25, LCM = 300

Cross-check: 100 × 75 ÷ 25 = 300 ✓ — the two-number identity agrees.

Common mistakes — and how to dodge them

Stopping at the first remainder

Euclid's algorithm repeats until the remainder is 0 — the GCD is the LAST non-zero remainder, not the first. Stopping after 180 = 48 × 3 + 36 would report 36, which does not divide 48. This gcd calculator shows every step until the remainder hits 0.

Taking the highest powers for the GCD

The GCD takes the LOWEST power of each prime; the highest powers give the LCM. For 48 and 180, the GCD needs 2² (not 2⁴) and 3¹ (not 3²). Mixing the two up swaps the answers — the page shows both side by side so the pair is never confused.

Assuming coprime means "no common factors"

Coprime numbers still share the factor 1 — that is what "GCD = 1" means. 17 and 23 are both prime, so 1 is genuinely their greatest common divisor, and their LCM is simply their product, 391.

GCD Calculator — questions

What is the greatest common divisor?

The largest whole number that divides every input with no remainder: GCD(48, 180) = 12, because 12 divides both and nothing larger does. It is the number you need for simplifying fractions, reducing ratios, and splitting things into equal groups.

How does this gcd calculator verify its answer?

Two independent routes, both computed: Euclid's algorithm (repeated division with remainder) and prime factorization (lowest powers of each prime). The two answers must agree, the LCM is tested by division, and for two numbers the identity LCM × GCD = a × b is checked too.

What is the difference between GCD and GCF?

None — GCD (greatest common divisor) and GCF (greatest common factor) are two names for the same number. US textbooks usually say GCF; the rest of the world usually says GCD. This page answers to both names.

What happens with negative numbers?

Signs are dropped first, by the standard convention: divisors do not depend on sign, so GCD(−48, 180) is GCD(48, 180) = 12. The steps show the absolute-value step openly, so nothing is hidden.

What about zero?

GCD(0, 12) = 12 — every number divides 0, so the GCD is the other number. But GCD(0, 0) is undefined (every number divides 0, so there is no greatest one) and is refused. The LCM is not defined when 0 is among the inputs.

Is the gcd calculator free?

Yes — free, no sign-up, no app, full steps and verification included on every problem.

Keep solving

A note on honest use: VerifySolve is built for learning. Use the steps to understand the method, then close the tab and try one on your own — that is where the grade actually comes from. If your teacher or school has a policy on calculators, follow it.