Euclid’s Algorithm: GCD By Repeated Remainders

Find a gcd fast without factoring by repeatedly taking remainders until the remainder hits $0$. You will see why the numbers shrink so quickly, how to run the steps reliably, and how the same work can also produce $ax+by=\gcd(a,b)$.

Factoring feels like the natural way to find a greatest common divisor, until the numbers get big and the whole plan collapses. Euclid’s algorithm sidesteps factoring completely. It uses one move, take a remainder, and each move makes the numbers smaller. The surprise is that remainders are not a hack. They preserve the information a gcd cares about while discarding everything else.

The shortcut is remainders

The gcd of two numbers cares about what divides them both. When you replace a big number with its remainder after dividing by the smaller number, you keep the set of common divisors the same, but you usually shrink the problem dramatically.

To make the remainder idea feel concrete, it helps to see it as repeated subtraction. Dividing $360$ by $84$ leaves the same remainder as subtracting $84$ over and over until you cannot anymore. That leftover is the part that still might share a divisor with $84$.

Try the remainder picture below and notice how quickly the leftover drops compared to the original number.

Rule of thumb
If you can replace a number by something smaller without changing which numbers divide it, you are getting closer to the gcd.

What greatest common divisor really means

A divisor of $a$ is a number that goes into $a$ with no remainder. You will also see this written as $d\mid a$, read as $d$ divides $a$. A common divisor of $a$ and $b$ divides both. The greatest common divisor (gcd) is the largest positive common divisor.

Two edge cases are worth locking in early because they keep the algorithm from feeling like magic later.

• If $a=b$, then $\gcd(a,b)=a$.
• If $b=0$, then $\gcd(a,0)=a$.

That second one is not a special trick. Every number divides $0$, since $0=a\cdot 0$. So the common divisors of $a$ and $0$ are exactly the divisors of $a$, and the greatest of those is $a$.

If you want quick definitions and edge case reminders as you read, open the mini-cards here.

Why $\gcd(a,b)=\gcd(b,a\bmod b)$

Euclid’s algorithm rests on one identity.

Explanation: If $a=bq+r$ with $0\le r<b$, then $\gcd(a,b)=\gcd(b,r)$. Any number that divides both $a$ and $b$ also divides $r=a-bq$. Any number that divides both $b$ and $r$ also divides $a=bq+r$. So the sets of common divisors match.

The line $a=bq+r$ is the division algorithm. It says when you divide $a$ by $b$, you get a quotient $q$ and a remainder $r$. The remainder $r$ is exactly $a\bmod b$.

The key is the subtraction idea hiding inside it. Since $r=a-bq$, you get $r$ by taking $a$ and subtracting a whole-number multiple of $b$. Subtracting a multiple of $b$ cannot change whether something divides both numbers.

Use the annotated equation below to track which pieces matter for divisibility.

Once you accept this identity, the algorithm is just applying it repeatedly until the remainder becomes $0$.

Running Euclid’s algorithm by hand

Euclid’s algorithm is a loop with a clean stopping rule.

Start with $a$ as the larger number and $b$ as the smaller positive number.

• Divide $a$ by $b$ to get a remainder $r$.
• Replace $(a,b)$ with $(b,r)$.
• Stop when $r=0$. The gcd is the last nonzero remainder, which is the current $b$.

A table keeps you from losing track, especially when the quotients change from step to step. Each row is one division $a=bq+r$. The moment you see $r=0$, you do not need any more work.

Fill in the iteration table here, and watch how the last nonzero remainder gets singled out.

The quotients $q$ are not the goal. They are just bookkeeping that lets you produce the remainder reliably.

Stopping rule
When the remainder hits $0$, the current divisor is the gcd. Not the $0$, not the previous dividend.

Why it always stops

Each remainder is smaller than the number you divided by. If you start with $b>0$, the remainders form a strictly decreasing sequence of nonnegative integers:

$$b>r_1>r_2>\cdots\ge 0.$$

A strictly decreasing list of nonnegative integers cannot go on forever, so eventually a remainder becomes $0$ and the algorithm terminates.

How many steps should you expect? Usually not many.

The numbers tend to shrink fast because remainders are bounded by what you are dividing by. The slowest case happens when the remainders shrink as little as possible each time. That pattern is tied to consecutive Fibonacci numbers, and even then the step count grows only logarithmically with the size of the inputs. For beginner intuition, read that as doubling the size of the inputs adds only a small number of extra remainder steps.

Extended Euclid preview

Plain Euclid gives you $d=\gcd(a,b)$. Extended Euclid gives more. It finds integers $x$ and $y$ such that

$$ax+by=d.$$

This looks mysterious until you notice it is just undoing the remainder steps. Each remainder was built from the previous two numbers using a subtraction of a multiple. Working backward turns the final gcd into a combination of the original inputs.

Why care about $ax+by=d$.

• It proves the gcd really is the smallest positive number you can build from $a$ and $b$ using integer combinations.
• When $d=1$, it gives a way to find a modular inverse, the number that multiplies by $a$ to make $1$ modulo $b$.

Compare plain output versus extended output here so you can see what extra information appears.

You do not need extended Euclid to compute a gcd, but it is the same story with one extra layer of bookkeeping.

Where this shows up

Reducing fractions is the everyday use. To simplify $\frac{a}{b}$, compute $d=\gcd(a,b)$ and divide top and bottom by $d$. Euclid’s algorithm makes that step fast even when $a$ and $b$ are large.

Modular arithmetic uses gcd as a gatekeeper. If $\gcd(a,m)=1$, then $a$ has a multiplicative inverse modulo $m$. If the gcd is larger than $1$, it does not. That single gcd check prevents a lot of confusion.

When you want to fact-check your gcd result without refactoring everything, try these quick tests.

• Your gcd must divide both original numbers.
• Your gcd cannot be larger than the smaller input.
• If you get a remainder wrong, later remainders often look too large. They should generally trend downward fast.

If you want a concrete next step, pick two numbers you care about from your own work, a fraction, a timestamp pair, anything, and run Euclid’s algorithm until you can do the remainder steps without hesitation. Speed comes from confidence in the stopping rule, not from mental arithmetic tricks.