Quick answer
The Euclidean algorithm finds the GCD by repeated division: gcd(a, b) = gcd(b, a mod b). For 48 and 18: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0, so the GCD is 6.
Enter two positive integers. The calculator returns the GCD and the division steps.
Related tools: Slope Calculator: Slope, angle, distance and line equation through two points. LCM Calculator: Least common multiple of two or more numbers. Factor Calculator: List every factor of a positive whole number.
How to use the Euclidean Algorithm Calculator
- Enter first number (a whole number, between 1 and 1000000000000).
- Enter second number (a whole number, between 1 and 1000000000000).
- Press Calculate to see the result, and use Reset to start again.
| Input | What to enter | Allowed values |
|---|---|---|
| First number | A whole number | ≥ 1, ≤ 1000000000000 |
| Second number | A whole number | ≥ 1, ≤ 1000000000000 |
Formula and method
Formula
gcd(a, b) = gcd(b, a mod b)
IEEE-754 double precision; shown to at most 6 decimal places.
Repeated division with remainder until the remainder is 0.
Worked examples
This example is verified: each one is an automated test case that the live calculator must reproduce exactly.
Example 1
Inputs: First number = 48; Second number = 18.
| Result | Value |
|---|---|
| GCD | 6 |
| Steps | 48 = 2 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0 |
The first line is the headline result (gCD). Below it the euclidean Algorithm Calculator lists steps, which describe the same case from other angles. IEEE-754 double precision; shown to at most 6 decimal places.
Why it works
Any common divisor of a and b also divides a mod b. Repeating shrinks the numbers until the remainder is zero, and the last non-zero remainder is the GCD. It takes about log₂ of the smaller number steps.
Extensions
The extended algorithm also finds integers x and y with ax + by = gcd, used in modular inverses and cryptography. It dates from Euclid's Elements, around 300 BC.
How the result changes with first number
Holding every other input at the first worked example, this table changes only first number. It shows how sensitive the answer is to that one value; each row was produced by running this calculator.
| First number | GCD | Steps |
|---|---|---|
| 24 | 6 | 24 = 1 × 18 + 6; 18 = 3 × 6 + 0 |
| 48 | 6 | 48 = 2 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0 |
| 96 | 6 | 96 = 5 × 18 + 6; 18 = 3 × 6 + 0 |
| 192 | 6 | 192 = 10 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0 |
What happens with invalid input
These messages are produced by the calculator itself, so you know what to fix.
- First number: entering "0" shows "First number must be at least 1." beside that field and no result.
Choosing between the Euclidean Algorithm Calculator and similar calculators
Each row shows what a related calculator on this site asks for and what it returns, so you can pick the one that matches your question.
| Calculator | You enter | It returns |
|---|---|---|
| [Slope Calculator](/math/slope-calculator/) | x₁, y₁ and x₂ | Slope |
| [LCM Calculator](/math/lcm-calculator/) | numbers | Least common multiple |
| [Factor Calculator](/math/factor-calculator/) | number | Factors |
| [Quadratic Formula Calculator](/math/quadratic-formula-calculator/) | a, b and c | Roots |
| [Log Calculator](/math/log-calculator/) | number x and base b | log base 2 of 8 |
Background: algebra
Many algebra calculators rest on the same ideas: write the problem in a standard form, identify the coefficients, apply the formula and check the answer by substituting it back. For a quadratic ax² + bx + c = 0 the roots are (−b ± √(b² − 4ac)) ÷ 2a, and the discriminant b² − 4ac decides the kind of roots: positive gives two real roots, zero gives one repeated root and negative gives two complex conjugate roots.
If a = 0 the equation is linear, not quadratic. A sign slip on the −b term shifts both roots by the same amount, so substitute your roots back to check.
Assumptions and limitations
- Positive integers
If a required value is empty, not a number, or outside its allowed range, the form marks that field with a message and shows no result instead of a misleading number. The automated checks deliberately try invalid entries for first number to confirm this.
Frequently asked questions
How many steps for 48 and 18?
Three divisions: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6 and 12 = 2 × 6 + 0.
Is it faster than listing factors?
Yes, especially for large numbers.
What if one number is zero?
If one number is zero the GCD is the other number, since gcd(a, 0) = a.
What does the Euclidean Algorithm Calculator calculate?
GCD with every division step shown. It returns GCD and Steps.
What formula does the Euclidean Algorithm Calculator use?
gcd(a, b) = gcd(b, a mod b). Repeated division with remainder until the remainder is 0.
What do I need to enter in the euclidean Algorithm Calculator?
You enter First number and Second number.
How is the result rounded or limited?
IEEE-754 double precision; shown to at most 6 decimal places. Positive integers.
What is an example of a euclidean Algorithm result?
With first number 48 and second number 18, the gCD is 6.
Where does the method come from?
The method follows: Euclid, Elements, Book VII, Prop. 2.
Related calculators
- Slope Calculator — Slope, angle, distance and line equation through two points.
- LCM Calculator — Least common multiple of two or more numbers.
- Factor Calculator — List every factor of a positive whole number.
- Quadratic Formula Calculator — Solve ax² + bx + c = 0, including complex roots.
- Log Calculator — Logarithm of a number to any base.
- GCF Calculator — Greatest common factor (greatest common divisor) of two or more numbers.
- Geometric Sequence Calculator — nth term and sum of a geometric sequence.
- Sum of Series Calculator — Sum of the first n integers, squares and cubes.
- Exponential Growth Calculator — Exponential growth over time at a constant percentage rate.
Sources
- Euclid, Elements, Book VII, Prop. 2
Content last reviewed 2026-11-04. Formulas and worked examples are checked by automated tests against independently computed values.