What does the Euclidean Algorithm Visualizer do?

It computes the greatest common divisor of any two positive integers and displays every step of the calculation. Each row of the visual chain is one division equation of the form dividend equals divisor times quotient plus remainder. Amber pills mark the remainders, dashed arrows show each remainder becoming the next divisor, and the final divisor is boxed in purple as the GCD.

Why does the Euclidean algorithm work?

The algorithm relies on the fact that the GCD of two numbers equals the GCD of the smaller one and the remainder after dividing the larger by the smaller. Replacing the pair this way preserves the set of common divisors and therefore the greatest one. Each step also strictly decreases the smaller number, so the process eventually reaches zero, at which point the partner number is the answer.

What do the dashed arrows in the diagram represent?

Each dashed arrow shows the core substitution of the algorithm. The remainder on one row becomes the divisor on the next row. Following the arrows top to bottom is following the algorithm's recursion visually. Hovering any remainder pill darkens its arrow and highlights its destination divisor with a purple ring.

Which inputs produce the longest chains?

Consecutive Fibonacci numbers produce the worst-case behavior of the Euclidean algorithm — the longest chains relative to the size of the numbers involved. Coprime pairs (GCD equal to 1) also tend to produce longer chains than non-coprime pairs of similar size, since the algorithm has to grind all the way down to a remainder of 1 before terminating.

Euclidean Algorithm

Euclidean Algorithm Visualizer

Type any two whole numbers, or try a preset. Each line below divides and keeps the leftover — the pair shrinks until nothing is left over, and the last divisor standing is the greatest common divisor.

a?b

remainder (the leftover) becomes the next divisor greatest common divisor

How the Euclidean algorithm works

The idea is older than algebra: the greatest common divisor of two numbers does not change if you replace the larger number with the remainder after dividing it by the smaller one.

Divide the bigger number by the smaller one and keep the remainder.
Replace the pair: the old divisor becomes the new dividend, the remainder becomes the new divisor.
Repeat. Each remainder is smaller than the last, so the process always ends.
When the remainder reaches 0, the divisor on that final line is the answer.

Hover any amber remainder above to see it drop down and become the divisor on the next line — that single move is the whole algorithm.

Getting Started with the Visualizer

Entering Numbers and Using Presets

Reading a Division Row

Following the Substitution Arrows

Hovering Remainders and Steps

The Result Banner and GCD Callout

What Is the Greatest Common Divisor?

Why the Algorithm Works

Special Cases and Corner Behavior

Related Concepts and Tools

Getting Started with the Visualizer

Open the page and a friendly banner appears at the top once you have two numbers entered. By default it launches with

a = 252

and

b = 105

— a classic textbook example where the greatest common divisor is

21

.

The visualizer has four main parts arranged top to bottom:

• Input controls — two number fields for

a

and

b

, plus a Random pair button and five preset pairs
• Result banner — large purple number showing the GCD, with a plain-language sentence explaining what it means
• Division chain — a vertical stack of equations of the form

a = b \cdot q + r

, each step shrinking the pair, with amber remainder pills and dashed arrows connecting each remainder to the next divisor
• Steps list and legend — a side panel listing every division as plain text, plus a color legend

A collapsible "How the Euclidean algorithm works" panel sits at the bottom for the underlying mathematical idea.

Entering Numbers and Using Presets

Type any two positive whole numbers into the

a

and

b

fields. The visualizer recomputes the entire chain instantly on every keystroke. If

a < b

, the algorithm internally swaps them — the larger of the two is always the first dividend.

For exploration without typing, three quick options live next to the input fields:

• Random pair — generates two random integers between 12 and 480 and runs the algorithm on them. Useful for sampling the variety of chain lengths that arise from different inputs.
• Five preset pairs — curated examples spanning easy and interesting cases:

(252, 105)

giving GCD

21

(462, 198)

giving

66

(1071, 462)

giving

21

(56, 84)

where one input divides the other, and

(35, 54)

which are coprime (GCD

1

).

The presets are deliberately chosen to demonstrate the algorithm's qualitative behaviors: coprime cases that grind through many steps, divisor cases that finish in one step, and mid-sized examples that produce a satisfyingly visual chain of about 3–5 rows.

Reading a Division Row

Each row of the chain shows one application of the division algorithm:

\text{dividend} = \text{divisor} \cdot \text{quotient} + \text{remainder}

Read left to right: the dividend is the larger of the current pair, the divisor is the smaller, the quotient is how many whole times the divisor fits into the dividend, and the remainder is what is left over.

The remainder is highlighted in an amber pill to draw the eye — it is the key piece that becomes the divisor of the *next* row. The final divisor, when the remainder finally hits zero, is shown in a purple box with a "gcd = N" callout below it. The terminating zero remainder appears as a dashed gray pill with an italic "stop" label, indicating that the algorithm has finished.

Every numerical field is rendered in monospace so the rows align vertically. The visual chain reads top to bottom as a step-by-step computation that the eye can follow without effort.

Following the Substitution Arrows

Between every pair of consecutive rows, a dashed amber Bezier arrow sweeps from the remainder pill of one row down to the divisor position of the next. This is the visual representation of the core algorithmic substitution:

\text{new pair} = (\text{old divisor}, \text{old remainder})

The arrow makes the substitution concrete. You can literally see the number that was a remainder in row

i

become the divisor in row

i + 1

, repeating until a remainder of zero finally appears. The whole algorithm is captured by that single recurring move.

The arrows are deliberately subtle by default — drawn in the same amber as the remainder pills — so they read as decoration when you scan but become useful when you study a particular step. Hovering a remainder darkens its arrow and turns it purple, making the connection unmistakable.

Hovering Remainders and Steps

Two coordinated hover interactions help you trace the algorithm:

• Hover an amber remainder pill — its arrow lights up in purple, and the divisor on the next row gets a purple ring around it. Both endpoints of the substitution glow together, letting you confirm which remainder becomes which divisor.
• Hover an entry in the side Steps list — the same row in the diagram lights up. Useful when you want to inspect a specific step from the textual summary without scrolling.

Both hover targets connect the textual representation (numbered list of equations on the right) to the graphical chain (the diagram in the center). Wherever your attention lands, the corresponding parts in the other view highlight automatically.

The hover state is also exposed as a native browser tooltip on the SVG elements, so screen readers and accessibility tools can convey the substitution relationship in plain text.

The Result Banner and GCD Callout

Above the diagram, a purple banner shows the result in three forms simultaneously:

• A large standalone number — the GCD itself, in big bold purple
• A monospace equation —

\gcd(a, b) = N

in the canonical mathematical form
• A plain-language sentence — "The largest number that divides both

a

and

b

evenly is

N

(found in

k

steps)"

The triple presentation is deliberate. The standalone number is for someone who just wants the answer. The equation is for someone copying the result into a homework problem. The sentence is for a beginner first encountering the concept and needing to know what "greatest common divisor" actually means.

Below the diagram, the final divisor — the GCD — appears in a purple-bordered box with a callout line and the label "gcd = N" beneath it. This visual punctuation marks the chain's endpoint and connects the diagram back to the banner.

What Is the Greatest Common Divisor?

The greatest common divisor (GCD) of two integers is the largest integer that divides both of them with no remainder. Equivalently, it is the largest member of their common set of divisors.

For small numbers, you could find the GCD by listing every divisor of each number and picking the biggest one they share. For example:

• Divisors of

12

1, 2, 3, 4, 6, 12

• Divisors of

18

1, 2, 3, 6, 9, 18

• Common divisors:

1, 2, 3, 6

• Greatest common divisor:

\gcd(12, 18) = 6

This naive approach works but becomes slow for large numbers. The Euclidean algorithm — the method visualized here — finds the GCD without ever listing divisors. For

\gcd(252, 105)

it takes only three division steps, regardless of how many divisors

252

and

105

actually have.

The GCD is foundational for simplifying fractions, modular arithmetic, and number theory. Two numbers with GCD equal to

1

are called coprime — they share no common factors and are in some sense "as different as possible" multiplicatively.

Why the Algorithm Works

The Euclidean algorithm rests on a single mathematical fact, older than algebra itself:

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

In words: the greatest common divisor of two numbers stays the same if you replace the larger number with its remainder after division by the smaller. This is the invariant that the algorithm preserves at every step.

The argument is short. Any common divisor of

a

and

b

also divides

a - q \cdot b = r

, so it is a common divisor of

b

and

r

as well. Going the other way, any common divisor of

b

and

r

divides

b \cdot q + r = a

, so it is a common divisor of

a

and

b

. The two pairs have *exactly the same* set of common divisors, hence the same greatest common divisor.

The algorithm terminates because every step strictly decreases the smaller of the two numbers. A strictly decreasing sequence of non-negative integers must eventually reach zero. When it does, the partner — the last nonzero remainder — is the GCD, because

\gcd(d, 0) = d

Special Cases and Corner Behavior

A few input patterns produce notably short or long chains:

• One number divides the other — try the preset

(56, 84)

. The first division gives

84 = 56 \cdot 1 + 28

, then

56 = 28 \cdot 2 + 0

, and the algorithm stops at GCD

28

after just two steps. Whenever the smaller number is a divisor of the larger, the chain terminates in one or two rows.

• Coprime numbers — try the preset

(35, 54)

. The GCD is

1

, and the chain works through several reductions before finally hitting a remainder of

1

and then

0

. Coprime pairs tend to produce the *longest* chains relative to the size of the numbers.

• Consecutive Fibonacci numbers — try entering, e.g.,

89

and

144

. These pairs produce the absolute worst-case behavior of the algorithm and the longest chains for their magnitude. The reason is built into the recursive definition of Fibonacci numbers themselves.

• Equal numbers — entering the same number twice gives a one-step chain ending immediately at the GCD, which is that number.

Running the algorithm on a few of these intentionally extreme cases gives a feel for how the input size relates to the chain length — and why the Euclidean algorithm is considered remarkably efficient even on enormous inputs.

Related Concepts and Tools

Greatest Common Divisor — the mathematical concept the visualizer computes; the theoretical companion page to this tool.

Least Common Multiple (LCM) — the dual concept, related to the GCD by

\text{lcm}(a, b) = a \cdot b / \gcd(a, b)

.

Division Algorithm — the basic theorem that for any positive integers

a

and

b

, there exist unique

q

and

r

with

0 \leq r < b

such that

a = b \cdot q + r

. Every row of the visualizer is one application of this.

Coprime Integers — pairs with GCD equal to

1

; foundational for modular arithmetic and number theory.

Prime Factorization — an alternative route to the GCD via factoring both numbers and multiplying their shared prime powers. Slower for large numbers than the Euclidean algorithm but more transparent for small ones.

Bezout's Identity — the extended Euclidean algorithm finds integers

x

and

y

such that

ax + by = \gcd(a, b)

. A natural follow-up tool to this one.

Modular Arithmetic — the GCD underlies which numbers are invertible modulo

n

and is the foundation of many cryptographic schemes.

Fibonacci Numbers — the worst-case inputs for the Euclidean algorithm, related to it through deep recursive structure.