The Euclidean algorithm is a systematic method for finding the greatest common divisor of two integers. It repeatedly divides the larger number by the smaller number, replaces the pair with the divisor and remainder, and continues until the remainder becomes zero.
The last nonzero remainder is the greatest common divisor.
For example, to find the GCD of 252 and 105:
252 = 105 × 2 + 42
105 = 42 × 2 + 21
42 = 21 × 2 + 0
The last nonzero remainder is 21.
Therefore:
GCD(252, 105) = 21
The Euclidean algorithm is one of the fundamental computational ideas in arithmetic and number theory because it converts a potentially difficult factor problem into a short sequence of divisions.
What Is the Euclidean Algorithm?
The Euclidean algorithm finds the largest positive integer that divides two given integers exactly.
Suppose two positive integers are:
a and b
with:
a > b > 0
Divide a by b:
a = bq + r
where:
q = quotient
r = remainder
and:
0 ≤ r < b
If:
r = 0
then b is the greatest common divisor.
If the remainder is not zero, replace:
(a, b)
with:
(b, r)
and repeat.
This repeated use of division is the core of the algorithm.
Euclidean Algorithm Formula
The basic step is:
a = bq + r
Then:
GCD(a, b) = GCD(b, r)
The process continues:
a = bq₁ + r₁
b = r₁q₂ + r₂
r₁ = r₂q₃ + r₃
and so on until:
rₙ₋₁ = rₙqₙ₊₁ + 0
The answer is:
GCD(a, b) = rₙ
where rₙ is the final nonzero remainder.
Why the Euclidean Algorithm Works
Suppose:
a = bq + r
Any integer that divides both a and b also divides:
a – bq
But:
a – bq = r
So every common divisor of a and b is also a common divisor of b and r.
The reverse is also true. If an integer divides both b and r, then it divides:
bq + r = a
Therefore the sets of common divisors are the same.
That gives:
GCD(a, b) = GCD(b, r)
Repeating this reduction eventually produces a much smaller pair of integers without changing their greatest common divisor.
Worked Example: GCD of 48 and 18
Find:
GCD(48, 18)
Divide 48 by 18:
48 = 18 × 2 + 12
Now replace the pair (48, 18) with:
(18, 12)
Divide again:
18 = 12 × 1 + 6
Replace the pair with:
(12, 6)
Then:
12 = 6 × 2 + 0
The remainder is now zero.
The last nonzero remainder was:
6
Therefore:
GCD(48, 18) = 6
You can verify this from their common factors:
Factors shared by 48 and 18 = 1, 2, 3, 6
The largest is 6.
Worked Example: GCD of 270 and 192
Start with:
270 = 192 × 1 + 78
Then:
192 = 78 × 2 + 36
Continue:
78 = 36 × 2 + 6
Then:
36 = 6 × 6 + 0
The final nonzero remainder is:
6
Therefore:
GCD(270, 192) = 6
Notice that the integers become smaller quickly. This is one reason the Euclidean algorithm is efficient even when the starting numbers are large.
Step-by-Step Euclidean Algorithm
For positive integers a and b:
- Put the larger integer first.
- Divide the larger integer by the smaller one.
- Record the remainder.
- Replace the larger number with the previous divisor.
- Replace the smaller number with the remainder.
- Repeat until the remainder is zero.
- Take the last nonzero remainder as the GCD.
The arithmetic is repeated, but the logic never changes.
Example With Consecutive Integers
Find:
GCD(101, 100)
Start:
101 = 100 × 1 + 1
Then:
100 = 1 × 100 + 0
The last nonzero remainder is:
1
Therefore:
GCD(101, 100) = 1
This illustrates a broader fact: consecutive positive integers are always relatively prime.
Their only positive common factor is 1.
Example With One Number Dividing the Other
Find:
GCD(84, 28)
The first division is:
84 = 28 × 3 + 0
The remainder is already zero.
Therefore:
GCD(84, 28) = 28
Whenever the smaller number divides the larger number exactly, the smaller number is the GCD.
The Euclidean Algorithm and Divisibility
The stopping condition depends on exact divisibility.
When:
a mod b = 0
the divisor b divides a with no remainder.
At that point:
GCD(a, b) = b
The shortcuts covered by divisibility rules may reveal obvious divisors, but the Euclidean algorithm does not require special divisibility patterns. It works systematically with the actual remainders.
Euclidean Algorithm Using Remainder Notation
Instead of writing the full division equation, the procedure may be written with modulo notation:
r = a mod b
Then repeat:
a ← b
b ← r
until:
b = 0
The remaining value of a is the GCD.
For example:
252 mod 105 = 42
105 mod 42 = 21
42 mod 21 = 0
Therefore:
GCD(252, 105) = 21
Both formats describe exactly the same algorithm.
Pseudocode for the Euclidean Algorithm
A compact form is:
while b ≠ 0
r = a mod b
a = b
b = r
After the loop:
GCD = a
This makes the algorithm straightforward to implement computationally because every iteration reduces the size of the second value.
Example: GCD of 1071 and 462
Calculate:
1071 = 462 × 2 + 147
Then:
462 = 147 × 3 + 21
Then:
147 = 21 × 7 + 0
Therefore:
GCD(1071, 462) = 21
Only three divisions were required.
Why the Numbers Get Smaller
At every nonterminal step:
0 < r < b
The new pair is:
(b, r)
so the second number is strictly smaller than the previous divisor.
Because positive integers cannot decrease indefinitely, the process must eventually reach remainder zero.
This guarantees termination for positive integer inputs.
Euclidean Algorithm vs. Listing Factors
You could find the GCD of 84 and 126 by listing all factors.
Factors of 84 include:
1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84
Factors of 126 include:
1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126
The largest shared factor is:
42
The Euclidean algorithm reaches the same result more directly:
126 = 84 × 1 + 42
84 = 42 × 2 + 0
Therefore:
GCD(126, 84) = 42
For larger numbers, repeated division is usually much more efficient than creating complete factor lists.
Euclidean Algorithm vs. Prime Factorization
Another way to find a GCD is through prime factorization.
For example:
84 = 2² × 3 × 7
126 = 2 × 3² × 7
The common prime factors using the smaller exponent of each are:
2 × 3 × 7 = 42
Therefore:
GCD = 42
Prime factorization works well when the prime decompositions are easy to obtain.
The Euclidean algorithm avoids needing those decompositions entirely.
That distinction becomes particularly valuable for large integers whose prime factors may be difficult to find.
Euclidean Algorithm and the Greatest Common Factor
The terms greatest common divisor and greatest common factor are commonly used for the same positive integer.
For example:
GCD(72, 120) = 24
and:
GCF(72, 120) = 24
The dedicated greatest common factor topic focuses on GCF calculation methods and interpretation. The Euclidean algorithm is one particularly efficient method for obtaining that value.
Example: GCD of 72 and 120
Place the larger integer first:
120 = 72 × 1 + 48
Then:
72 = 48 × 1 + 24
Then:
48 = 24 × 2 + 0
Therefore:
GCD(72, 120) = 24
Verify:
72 ÷ 24 = 3
120 ÷ 24 = 5
So 24 divides both exactly.
Euclidean Algorithm With Large Integers
Find:
GCD(17,365, 6,825)
Start:
17,365 = 6,825 × 2 + 3,715
Then:
6,825 = 3,715 × 1 + 3,110
Then:
3,715 = 3,110 × 1 + 605
Then:
3,110 = 605 × 5 + 85
Then:
605 = 85 × 7 + 10
Then:
85 = 10 × 8 + 5
Finally:
10 = 5 × 2 + 0
Therefore:
GCD(17,365, 6,825) = 5
Even though the starting integers are large, the method only requires repeated integer division.
Using the Euclidean Algorithm for More Than Two Numbers
To find the GCD of three integers, compute the GCD of two first, then combine the result with the third.
For example:
GCD(84, 126, 210)
First:
GCD(84, 126) = 42
Then:
GCD(42, 210)
Since:
210 = 42 × 5
we get:
GCD(42, 210) = 42
Therefore:
GCD(84, 126, 210) = 42
The method can be extended similarly to additional integers.
Coprime Numbers
Two positive integers are coprime when:
GCD(a, b) = 1
For example, find:
GCD(35, 64)
Use the algorithm:
64 = 35 × 1 + 29
35 = 29 × 1 + 6
29 = 6 × 4 + 5
6 = 5 × 1 + 1
5 = 1 × 5 + 0
Therefore:
GCD(35, 64) = 1
So 35 and 64 are coprime.
Neither number needs to be prime individually.
Euclidean Algorithm and Fractions
A fraction can be simplified by dividing numerator and denominator by their GCD.
Consider:
252 / 105
The Euclidean algorithm gave:
GCD(252, 105) = 21
Divide both by 21:
252 ÷ 21 = 12
105 ÷ 21 = 5
Therefore:
252 / 105 = 12 / 5
The GCD ensures that the reduced numerator and denominator no longer share a positive factor greater than 1.
Euclidean Algorithm and LCM
For positive integers a and b:
GCD(a, b) × LCM(a, b) = a × b
So:
LCM(a, b) = (a × b) / GCD(a, b)
Suppose:
a = 48
b = 18
The Euclidean algorithm gives:
GCD(48, 18) = 6
Then:
LCM(48, 18) = (48 × 18) / 6
= 864 / 6
= 144
Therefore:
LCM(48, 18) = 144
The dedicated LCM page focuses on least common multiples themselves; the Euclidean algorithm supplies the GCD used in this relationship.
The Extended Euclidean Idea
The ordinary Euclidean algorithm finds the GCD.
A related extension can express the GCD as an integer combination of the original values:
GCD(a, b) = ax + by
for suitable integers x and y.
For example:
GCD(35, 12) = 1
and one representation is:
1 = 35 × (-1) + 12 × 3
because:
-35 + 36 = 1
This extension is useful in areas such as modular arithmetic, but the core Euclidean algorithm only requires the repeated remainder process.
Example: Reconstructing the GCD
Take:
99 and 78
Run the algorithm:
99 = 78 × 1 + 21
78 = 21 × 3 + 15
21 = 15 × 1 + 6
15 = 6 × 2 + 3
6 = 3 × 2 + 0
Therefore:
GCD(99, 78) = 3
The answer can be checked directly:
99 ÷ 3 = 33
78 ÷ 3 = 26
Both quotients are integers.
Handling Zero
For a positive integer a:
GCD(a, 0) = a
For example:
GCD(27, 0) = 27
This is consistent with divisibility because every nonzero integer divides 0, while the positive divisors common to 27 and 0 are exactly the divisors of 27.
Algorithmically, if the second input is already zero, no division steps are necessary.
Negative Inputs
The GCD is normally reported as a nonnegative value.
Therefore:
GCD(-48, 18) = 6
GCD(48, -18) = 6
GCD(-48, -18) = 6
A practical calculation can use absolute values:
GCD(|a|, |b|)
and then apply the ordinary algorithm.
The Euclidean Algorithm and Exponents
Exponents can describe prime-factor structures compactly, such as:
72 = 2³ × 3²
but the Euclidean algorithm does not require powers or prime decomposition.
That is one of its key advantages. It finds a GCD directly from division and remainders even when the factorization of the input integers is unknown.
The Euclidean Algorithm and Factorial Values
A factorial can produce very large integers quickly.
For example:
8! = 40,320
If a problem asks for the GCD of a factorial-derived integer and another integer, the Euclidean algorithm can still be applied to the resulting values.
The factorial operation creates the integer; the Euclidean algorithm answers the separate question of their greatest common divisor.
The Euclidean Algorithm and Entropy
The entropy formula uses probabilities and logarithms to quantify uncertainty, while the Euclidean algorithm operates on integers through quotients and remainders.
Both are mathematical algorithms or formulas, but their domains are fundamentally different. The Euclidean algorithm should therefore be used specifically for greatest-common-divisor problems rather than for general numerical calculations.
Common Euclidean Algorithm Mistakes
A frequent mistake is keeping the old dividend after calculating a remainder.
If:
252 = 105 × 2 + 42
the next pair is:
105 and 42
not:
252 and 42
Another mistake is stopping one line too early. The GCD is the last nonzero remainder, not the final remainder of zero.
For:
84 = 30 × 2 + 24
30 = 24 × 1 + 6
24 = 6 × 4 + 0
the GCD is:
6
not 0.
Incorrect quotient arithmetic can also produce a wrong remainder. Each line should satisfy:
dividend = divisor × quotient + remainder
Finally, for positive divisors, a valid remainder must be smaller than the divisor.
How to Check Every Step
Suppose a step is:
391 = 102 × 3 + 85
Check:
102 × 3 = 306
Then:
306 + 85 = 391
The step is valid.
Next:
102 = 85 × 1 + 17
Check:
85 + 17 = 102
Finally:
85 = 17 × 5 + 0
Therefore:
GCD(391, 102) = 17
Checking each division equation prevents an early arithmetic error from propagating through the entire algorithm.
Frequently Asked Questions
What is the Euclidean algorithm?
The Euclidean algorithm is a method for finding the greatest common divisor of two integers by repeatedly replacing the larger pair with a divisor and remainder.
What is the Euclidean algorithm formula?
The central division relationship is:
a = bq + r
and the key property is:
GCD(a, b) = GCD(b, r)
When does the Euclidean algorithm stop?
It stops when the remainder becomes zero.
The previous nonzero remainder is the GCD.
What is the GCD of 48 and 18 using the Euclidean algorithm?
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0
Therefore:
GCD(48, 18) = 6
Why does replacing the numbers with the divisor and remainder work?
Because the original pair and the new pair have exactly the same common divisors.
Can the Euclidean algorithm work with large numbers?
Yes. It is particularly useful for large integers because the remainders usually shrink quickly.
Can the Euclidean algorithm show that two numbers are coprime?
Yes. If the final nonzero remainder is 1, their GCD is 1 and the integers are coprime.
Is the Euclidean algorithm the same as prime factorization?
No. Prime factorization decomposes integers into prime factors. The Euclidean algorithm finds a GCD directly from repeated division and does not require factorization.
What happens if one number is zero?
For nonzero a:
GCD(a, 0) = |a|
Can the Euclidean algorithm be used for three numbers?
Yes. Find the GCD of the first two numbers and then find the GCD of that result with the third.
Final Example
Find:
GCD(899, 493)
Start:
899 = 493 × 1 + 406
Then:
493 = 406 × 1 + 87
Continue:
406 = 87 × 4 + 58
87 = 58 × 1 + 29
58 = 29 × 2 + 0
The last nonzero remainder is:
29
Therefore:
GCD(899, 493) = 29
Check:
899 ÷ 29 = 31
493 ÷ 29 = 17
Both divisions are exact.
The Euclidean algorithm works by repeatedly replacing a difficult GCD problem with a smaller equivalent one until the common divisor becomes immediately visible.
