Euclidean Algorithm GCD Calculator

Calculator Input

Formula Used

Euclidean rule: gcd(a, b) = gcd(b, a mod b). The process stops when the remainder becomes zero.

Final gcd: The last nonzero divisor is the greatest common divisor.

Extended rule: ax + by = gcd(a, b). The values x and y are Bézout coefficients.

LCM rule: lcm(a, b) = |a × b| ÷ gcd(a, b), when the gcd is not zero.

Modular inverse: If gcd(a, m) = 1, then the coefficient of a gives the inverse of a modulo m.

How To Use This Calculator

Enter the first integer in the first field.
Enter the second integer in the second field.
Add optional extra integers for a multi-number gcd and lcm.
Press the calculate button.
Read the result box above the form.
Review the quotient and remainder table.
Use the CSV or PDF button to save your result.

Example Data Table

First Number	Second Number	GCD	LCM	Coprime?	Short Step Path
252	105	21	1260	No	252 → 105 → 42 → 21
391	299	23	5083	No	391 → 299 → 92 → 23
35	64	1	2240	Yes	35 → 64 → 35 → 29 → 6 → 5 → 1

Euclidean Algorithm GCD Calculator Guide

The Euclidean algorithm is a trusted way to find the greatest common divisor. It works fast, even when the numbers are large. Instead of testing every possible factor, it repeats a simple division step. Each step replaces the larger number with the smaller number, and replaces the smaller number with the remainder.

Why The Method Is Useful

This calculator is helpful for arithmetic, algebra, cryptography, fractions, modular work, and contest practice. It shows the final gcd and the full path used to reach it. That makes the answer easier to verify. It also helps students see why the method stops when the remainder becomes zero.

Advanced Outputs

The tool also calculates the lcm for two numbers and for an optional list. When only two main numbers are entered, it shows extended Euclidean coefficients. These coefficients prove the gcd as a linear combination of the original values. If the gcd is one, the same work can identify a modular inverse.

Working With Many Values

You may enter extra integers separated by commas. The calculator folds them one by one. It first finds the gcd of the first two values. Then it finds the gcd of that result and the next value. The process continues until every value is used. The same idea applies to the lcm.

Step Tables And Exports

The quotient table is useful when you need a neat record. It lists the dividend, divisor, quotient, and remainder for each division. You can copy the result into notes, or download the data as a CSV file. The PDF button creates a printable summary for reports and assignments.

Interpreting The Result

A gcd of one means the numbers are coprime. They share no positive divisor except one. A larger gcd means each number can be divided by that value without a remainder. For fractions, divide numerator and denominator by the gcd to reduce them. For ratio work, the gcd gives the simplest whole number form.

Input Tips

Use positive or negative integers only. The calculator uses absolute values for divisor size, while keeping signs clear in coefficient work. Avoid decimals, because the gcd belongs to integers. Zero is allowed when the other value is not zero.

FAQs

What is the Euclidean algorithm?

It is a repeated division method for finding the greatest common divisor of two integers. It replaces the pair with the divisor and remainder until the remainder becomes zero.

What does GCD mean?

GCD means greatest common divisor. It is the largest positive integer that divides each given number without leaving a remainder.

Can this calculator handle negative numbers?

Yes. The gcd is reported as a nonnegative value. The extended coefficient result keeps signs clear for the original input values.

Can I calculate the gcd of more than two numbers?

Yes. Enter extra integers in the optional field. The calculator finds the gcd by folding the values one pair at a time.

What are Bézout coefficients?

They are integers x and y that satisfy ax + by = gcd(a, b). They prove the gcd through a linear combination.

When is a modular inverse available?

A modular inverse is available when the first number and modulus are coprime. That means their gcd must equal one.

Why is the LCM included?

The lcm is closely related to gcd. It is useful for fractions, schedules, repeating cycles, and common multiple problems.

What happens if one number is zero?

If one number is zero, the gcd is the absolute value of the other number. If both are zero, the gcd is undefined.