Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Find the GCD with the Euclidean Algorithm

Divide the larger number by the smaller and keep only the remainder. The pair (smaller number, remainder) has the same GCD, so repeat until the remainder is 00: the last nonzero remainder is the GCD.

Recognize the task

You need gcd⁡(a,b)\gcd(a, b) and the numbers are large or hard to factor: gcd⁡(1,212,540)\gcd(1{,}212, 540), gcd⁡(437,323)\gcd(437, 323), or reducing a fraction like 9251961\frac{925}{1961}. Test: if neither number factors quickly with the divisibility rules, use this method; it never needs a factorization.
The algorithm is introduced in the Euclidean algorithm section of the GCD lesson.

Steps

StepOn gcd⁡(1,212,540)\gcd(1{,}212, 540)
1Divide the larger number by the smaller. Write the division as dividend == divisor ⋅\cdot quotient ++ remainder, with the remainder between 00 and the divisor (how to compute a remainder).1212=540⋅2+1321212 = 540 \cdot 2 + 132
2Replace the pair by (divisor, remainder). Any number that divides both aa and bb also divides a mod ba \bmod b, so the GCD does not change.gcd⁡(1212,540)=gcd⁡(540,132)\gcd(1212, 540) = \gcd(540, 132)
3Repeat until the remainder is 0. Each remainder is smaller than the last divisor, so the numbers shrink and the process stops.540=132⋅4+12540 = 132 \cdot 4 + 12,   132=12⋅11+0\; 132 = 12 \cdot 11 + 0
4Read the last nonzero remainder. It is the divisor in the final division, the one that leaves remainder 00.gcd⁡(1212,540)=12\gcd(1212, 540) = 12

Worked examples

Example 1 · two divisions

short
84=36⋅2+1284 = 36 \cdot 2 + 12
divide the larger by the smaller
36=12⋅3+036 = 12 \cdot 3 + 0
divide the old divisor by the remainder
gcd⁡(84,36)=12\gcd(84, 36) = 12
last nonzero remainder

Example 2 · four divisions

longer chain
270=192⋅1+78270 = 192 \cdot 1 + 78
first division
192=78⋅2+36192 = 78 \cdot 2 + 36
new pair (192,78)(192, 78)
78=36⋅2+678 = 36 \cdot 2 + 6
new pair (78,36)(78, 36)
36=6⋅6+036 = 6 \cdot 6 + 0, so gcd⁡(270,192)=6\gcd(270, 192) = 6
remainder 00: stop

Example 3 · reducing a fraction

application
323437\dfrac{323}{437}:   437=323⋅1+114\; 437 = 323 \cdot 1 + 114
no small prime divides both
323=114⋅2+95323 = 114 \cdot 2 + 95,   114=95⋅1+19\; 114 = 95 \cdot 1 + 19
keep dividing
95=19⋅5+095 = 19 \cdot 5 + 0, so the GCD is 1919
remainder 00: stop
323÷19437÷19=1723\dfrac{323 \div 19}{437 \div 19} = \dfrac{17}{23}
divide top and bottom
Watch every division row in the Euclidean algorithm visualizer, or check the result with the GCF calculator.

See it happen

Picture a 1212×5401212 \times 540 rectangle. Cut off as many 540×540540 \times 540 squares as fit: two, leaving a 132×540132 \times 540 strip. Cut that strip into 132×132132 \times 132 squares: four, leaving a 132×12132 \times 12 strip, which splits exactly into 12×1212 \times 12 squares. Every square size along the way is a multiple of the last one, so the 12×1212 \times 12 square tiles the whole rectangle, and no larger square can. Each division in the algorithm is one round of cutting.

Common mistakes

Dividing the original number again

✗ after 1212=540⋅2+1321212 = 540 \cdot 2 + 132, divide 12121212 by 132132
✓ divide the old divisor by the remainder: 540=132⋅4+12540 = 132 \cdot 4 + 12

Reporting the last quotient

✗ 36=12⋅3+036 = 12 \cdot 3 + 0, so gcd⁡(84,36)=3\gcd(84, 36) = 3
✓ the GCD is the divisor in that row: gcd⁡(84,36)=12\gcd(84, 36) = 12

Answering 0

✗ the last remainder is 00, so the GCD is 00
✓ the answer is the last nonzero remainder, 1212