Step-by-step
Euclidean algorithm steps:
GCD Calculator
This tool calculates the greatest common divisor (GCD) of two integers and shows the Euclidean algorithm steps. GCD is also called GCF (greatest common factor) or HCF (highest common factor). Enter $a$ and $b$ (negatives allowed) to get a positive GCD, see how inputs are normalized, and follow each division step. Use it to simplify fractions, reduce ratios, and factor out common integer parts in algebra. For more number-structure topics like GCD, explore Number Theory.
Enter two integers to compute the GCD (greatest common divisor).
Integer values only. Decimals are not allowed.
You can use negative numbers too.
Optional third value
What Is the GCD?
The greatest common divisor (GCD) is the largest positive integer that divides two integers with no remainder. In many textbooks, you'll also see it called the greatest common factor (GCF) or highest common factor (HCF). If two numbers share no common factor except $1$, their GCD is $1$, and they are called coprime.
GCD is mainly used to keep numbers as small as possible while preserving the same value. That's why it shows up constantly in fraction reduction, ratio simplification, and factoring expressions in algebra.
Where You Use GCD in Algebra
GCD matters because it captures the strongest shared integer structure between two values. In algebra, that translates into three common tasks:
- Simplifying fractions: reduce numerator and denominator by their shared factor.
- Simplifying ratios: reduce both parts by the same greatest factor.
- Factoring expressions: pull out the biggest common integer factor to simplify an expression.
If your task is finding a common denominator (instead of reducing), that's usually an LCM job. Use the LCM Calculator for that. If you want to quickly check whether a number has no divisors other than $1$ and itself, use the Prime Checker.
How the Euclidean Algorithm Finds the GCD
The Euclidean algorithm is the standard method used to compute the GCD efficiently. It works by repeated division: divide the larger number by the smaller number, then replace the pair using the remainder. When the remainder becomes zero, the last non-zero remainder you saw is the GCD.
That's why the steps in the calculator look like a short chain of divisions. Each step shrinks the numbers without changing the final GCD.
$$a = bq + r \quad\Rightarrow\quad \gcd(a,b)=\gcd(b,r)$$
GCD is closely related to LCM. For nonzero integers, their relationship is: $$\gcd(a,b)\cdot \mathrm{lcm}(a,b)=|ab|$$ This is useful when you already know one of them and want the other, and it also explains why both concepts often appear together in algebra and fraction work.
How to Use the Result
Once you know the GCD, you can apply it directly in simplification:
- Reduce a fraction: divide both the numerator and denominator by the GCD to get the simplest form.
- Reduce a ratio: divide both parts of the ratio by the GCD to get the simplest ratio.
- Factor out a common integer: pull the GCD out of all integer coefficients to simplify an expression.
A useful mental check: after simplification, the new pair should have GCD $1$. That's how you know you've fully reduced it.
Input Rules and Edge Cases
This tool is designed for integers. Negative values are allowed, and the output is always reported as a positive GCD. If you enter a decimal, it is not treated as a standard integer GCD problem.
- If one input is $0$: the GCD is the absolute value of the other input.
- If both inputs are $0$: the GCD is undefined because every integer divides $0$.
- If the numbers are coprime: the GCD is $1$.
Worked Examples
Example 1: Basic Euclidean steps
Use this to see the Euclidean algorithm in its simplest form: repeated division until the remainder becomes $0$.
Find: $$\gcd(48,18)$$ This is a straightforward Euclidean algorithm case. We keep dividing and tracking the remainder until the remainder becomes $0$. The last non-zero remainder is the GCD.
Euclidean steps: $$48 = 18\cdot 2 + 12$$ $$18 = 12\cdot 1 + 6$$ $$12 = 6\cdot 2 + 0$$
The last non-zero divisor is $6$, so: $$\gcd(48,18)=6$$
Example 2: Reducing a fraction
Use this when you want a fraction in simplest terms. Divide numerator and denominator by their GCD.
Reduce: $$\frac{84}{126}$$ The fraction is simplest when the numerator and denominator share no common factor greater than $1$. So we compute the GCD of $84$ and $126$, then divide both by that value.
Steps: $$126 = 84\cdot 1 + 42$$ $$84 = 42\cdot 2 + 0$$
So $$\gcd(84,126)=42$$ and: $$\frac{84}{126}=\frac{84\div 42}{126\div 42}=\frac{2}{3}$$
Example 3: Factoring the greatest common integer
Use this when you want to factor out the largest shared integer from coefficients to simplify an algebraic expression.
Factor: $$12x + 18$$ In algebra, the GCD of the integer coefficients tells you the largest integer you can factor out cleanly. Once you factor it out, the remaining expression is simpler to work with.
Compute: $$\gcd(12,18)=6$$
Factor out $6$: $$12x + 18 = 6(2x + 3)$$
Keep exploring Mathematics or jump back to Calculators
Questions About the GCD Calculator
Quick answers about GCD, factors, and the Euclidean algorithm.
The GCD (greatest common divisor) of two integers is the largest positive integer that divides both numbers with no remainder.
It is a fast method to compute the GCD using repeated division: $gcd(a, b) = gcd(b, a \bmod b)$ until the remainder becomes $0$.
$gcd(a, 0) = |a|$. The only undefined case is $gcd(0, 0)$, because every number divides $0$.
Yes. The GCD is defined as a positive value, so the calculator uses absolute values.
You can reduce a fraction by dividing the numerator and denominator by their GCD.
GCD is the largest number that divides both integers. LCM is the smallest positive number that both integers divide into. GCD is used for reducing, while LCM is used for finding a common denominator.
Trusted by thousands of users every month. Fast, accurate and privacy-friendly tools.