Euclidean Algorithm

In one sentence: The Euclidean algorithm finds the largest number that divides two numbers evenly, by replacing the pair with a smaller pair again and again until the remainder is zero.

$\gcd(a, b) = \gcd(b,\ a \bmod b), \qquad \gcd(a, 0) = a$

Read it out loud: “The greatest common divisor of a and b equals the greatest common divisor of b and a mod b. Here a mod b is the remainder when a is divided by b. The greatest common divisor of a and zero is a. The symbol gcd stands for greatest common divisor.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Divides evenly: A number $d$ divides another number $a$ evenly when splitting $a$ into groups of $d$ leaves nothing over. For example, 3 divides 12 evenly, because 12 is four groups of 3 with nothing left. A number that divides $a$ this way is called a divisor of $a$ . The number 1 divides every whole number.
Common divisor and the greatest common divisor, $\gcd$: A common divisor of two numbers divides both of them evenly. The greatest common divisor, written $\gcd(a, b)$ , is the largest of these. For 12 and 18 the common divisors are 1, 2, 3 and 6, so $\gcd(12, 18) = 6$ . The name gcd stands for greatest common divisor.
Remainder and $a \bmod b$: The remainder is what is left after dividing as many full groups as possible. It is written $a \bmod b$ , and it is always smaller than $b$ . For example, $48 \bmod 18 = 12$ , because 48 holds two full groups of 18, which make 36, with 12 left over.
Multiple and least common multiple: A multiple of a number is that number times a whole number, such as 6, 12, 18 and so on for the number 6. The least common multiple of two numbers is the smallest number that is a multiple of both. It is a different idea from the greatest common divisor, because it finds the smallest shared multiple, not the largest shared divisor.

What each symbol means

Symbol	Meaning
$\gcd(a, b)$	The greatest common divisor: the largest whole number that divides both $a$ and $b$ with no remainder. It has no unit, because it counts a number of parts rather than a measured amount. For 48 and 18 it is 6.
$a$	A whole number, 0 or more, and the first number of the pair. It has no unit in the algorithm itself. If you are cutting strips, $a$ is the length of the first strip, and the GCD has the same length unit.
$b$	A whole number, 0 or more, and the second number of the pair. The rule replaces the pair $(a, b)$ with the smaller pair $(b, a \bmod b)$ , so $b$ becomes the new first number at each step.
$a \bmod b$	The remainder when $a$ is divided by $b$ : the leftover after taking as many full groups of $b$ as possible from $a$ . It is always less than $b$ , which is why the numbers keep shrinking at every step of the algorithm.

The formula piece by piece

$a \bmod b$: The remainder when $a$ is divided by $b$ . It is always smaller than $b$ . In the example, $48 \bmod 18 = 12$ , and 12 is smaller than 18, so the numbers shrink.
$(b,\ a \bmod b)$: The new pair. The old second number $b$ becomes the new first number, and the remainder becomes the new second number. In the example, the first step turns the pair (48, 18) into the new pair (18, 12).
$\gcd(a, b) = \gcd(b,\ a \bmod b)$: The key step in one line: the greatest common divisor of the old pair equals the greatest common divisor of the new pair. Nothing is lost, because the two pairs share exactly the same common divisors, so their largest one is the same.
$\gcd(a, 0) = a$: The stopping rule. When the second number is 0, the first number is the answer. Every number divides 0 evenly, so the largest common divisor of $a$ and 0 is $a$ itself.
$\gcd(a, b) = \gcd(b,\ a \bmod b), \qquad \gcd(a, 0) = a$: The whole formula in one sentence: the greatest common divisor of $a$ and $b$ equals the greatest common divisor of $b$ and the remainder $a \bmod b$ , and the greatest common divisor of $a$ and zero is $a$ .

What the formula is doing, and why

The greatest common divisor, or GCD, of two whole numbers is the largest number that divides both of them with no remainder. Listing every divisor of two large numbers and comparing the lists is slow. The Euclidean algorithm finds the GCD much faster. It replaces the pair $(a, b)$ with the pair $(b, a \bmod b)$ , which has the same GCD, and repeats until the remainder is 0.

Why does the GCD stay the same? Any number that divides both $a$ and $b$ also divides $a - qb$ for any whole number $q$ . The remainder $a \bmod b$ has this form, with $q$ equal to the number of full copies of $b$ in $a$ . So the common divisors of $a$ and $b$ are exactly the common divisors of $b$ and $a \bmod b$ , and the largest one is the same for both pairs.

Why does it stop? A remainder is always smaller than the divisor, so the numbers shrink at every step. Whole numbers cannot shrink forever, so the remainder must reach 0 after a finite number of steps. When the remainder is 0, the last nonzero number is the answer, since $\gcd(a, 0) = a$ . Euclid described this method in Book VII of his Elements, written around 300 BC.

Why is it fast? The number of division steps is at most about five times the number of digits in the smaller number, so two 100-digit numbers need at most about 500 steps. Listing the divisors of a 100-digit number would take far longer. The method works for any two whole numbers, and the special case of 0 and 0 is covered in the FAQ below.

An everyday picture

Imagine two paper strips, 48 cm and 18 cm long. Cut as many 18 cm pieces as you can from the long strip, and 12 cm is left over. Now the strips are 18 cm and 12 cm. Cut 12 cm from the 18 cm strip, and 6 cm is left. The 6 cm piece fits into the 12 cm strip exactly twice, so 6 cm is the longest piece that measures both strips evenly.

Worked example: GCD of 48 and 18

We want the greatest common divisor of $a = 48$ and $b = 18$ . That is the longest length that cuts both 48 and 18 into whole pieces with nothing left over. The algorithm repeats the remainder rule until the remainder is 0.

Divide the larger number by the smaller. We divide 48 by 18: $48 = 2 \cdot 18 + 12$ . Two full groups of 18 make 36, and 12 is left over, so $48 \bmod 18 = 12$ . The rule says $\gcd(48, 18) = \gcd(18, 12)$ , so we can work with the smaller pair instead.
Repeat with the new pair. Now we divide 18 by 12: $18 = 1 \cdot 12 + 6$ . One full group of 12 leaves 6, so $18 \bmod 12 = 6$ . The rule gives $\gcd(18, 12) = \gcd(12, 6)$ . The numbers keep getting smaller, which is why the process must end.
Repeat once more. Divide 12 by 6: $12 = 2 \cdot 6 + 0$ . Two full groups of 6 make exactly 12, so the remainder is 0. The rule gives $\gcd(12, 6) = \gcd(6, 0)$ .
Stop when the remainder is 0. With the pair $(6, 0)$ , the rule $\gcd(a, 0) = a$ says the answer is the first number, 6. The last nonzero remainder before 0 is the answer, because it is the largest number that fits into both earlier numbers with nothing left over.
Check that 6 really fits both numbers. $48 \div 6 = 8$ and $18 \div 6 = 3$ . Both results are whole numbers with nothing left over, so 6 is a common divisor. The algorithm guarantees that no larger common divisor exists.
Use the answer to simplify a fraction. Dividing the top and the bottom of $\frac{48}{18}$ by 6 gives $\frac{8}{3}$ . Both numbers shrank by the same factor, so the fraction keeps the same value, about 2.67.
Count the work. The algorithm used 3 division steps. Listing every divisor of 48 and of 18, and then finding the biggest one that appears in both lists, would take much longer even for numbers this small.

Answer: The greatest common divisor of 48 and 18 is 6. The algorithm needed 3 division steps and never listed a single divisor.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Stopping at the wrong number. The answer is the last nonzero remainder, which is 6 here. The 12 is a remainder too early, and the 0 is never the answer.
Confusing the GCD with the least common multiple. The GCD of 48 and 18 is 6, while their least common multiple is 144.
Testing every number up to the smaller one. That works for small numbers, but it is far slower than the Euclidean algorithm when the numbers have many digits.

Where you will meet it

Simplifying fractions: dividing the top and bottom of $\frac{48}{18}$ by their GCD, 6, gives $\frac{8}{3}$ .
RSA encryption, which checks that the public exponent shares no factor with $\varphi(n)$ by computing a GCD.
Finding modular inverses with the extended Euclidean algorithm, a version that also tracks the numbers needed to undo a multiplication with a remainder, which cryptography uses to build private keys.
Computer algebra and number libraries, which reduce fractions with very large numerators and denominators.

Questions people ask

Why does the algorithm stop when the remainder is 0?

When the remainder is 0, the last divisor divides the number before it with nothing left over. That divisor is the largest common divisor, and $\gcd(a, 0) = a$ records that final step.

What is the GCD of 0 and 0?

Every number divides 0, so there is no largest common divisor to pick. By convention the GCD of 0 and 0 is defined as 0.

Is the algorithm fast for huge numbers?

Yes. The number of steps grows with the number of digits, not with the size of the numbers. Even 100-digit numbers need at most about $5 \times 100 = 500$ division steps.

Modulo Operation: The modulo operation gives the leftover amount after you split one whole number into as many equal full groups of another number as you can.
RSA Encryption: RSA lets anyone lock a message with a public key while only the owner can unlock it with a private key, because undoing a product of two secret primes is very hard.