Skip to main content
Z

Euclidean Algorithm Visualizer — GCD Step by Step

Animated Euclidean algorithm — compute the GCD of two numbers step by step with the (a, b) → (b, a mod b) reduction. Runs in your browser.

Free No signup Client-side Privacy friendly Updated

/

Pseudocode

Run an operation to see its steps.

How to use

  1. 1 Enter two numbers separated by a comma (e.g. 48, 36) and press Compute GCD.
  2. 2 Watch each step replace (a, b) with (b, a mod b) until b becomes 0.
  3. 3 When b is 0, a holds the greatest common divisor.
  4. 4 Use Random for a new pair, or step through one division at a time.

Why use this tool

  • See the Euclidean algorithm — one of the oldest in mathematics — in action.
  • Understand why gcd(a, b) = gcd(b, a mod b) and why it terminates so quickly.
  • Watch the values shrink logarithmically until one reaches zero.
  • Runs entirely in your browser. No signup, no uploads.

Frequently asked questions

What is the Euclidean algorithm?

A method for computing the greatest common divisor (GCD) of two integers by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is zero.

What is the time complexity of the Euclidean algorithm?

O(log min(a, b)) — the number of steps is proportional to the number of digits, which is why it is extremely fast even for huge numbers.

Why does gcd(a, b) = gcd(b, a mod b)?

Any common divisor of a and b also divides a mod b (and vice versa), so the set of common divisors — and therefore the greatest one — is unchanged by the replacement.

What is the GCD used for?

Simplifying fractions, modular arithmetic, the extended Euclidean algorithm (modular inverses, RSA), and the least common multiple via lcm(a,b) = a·b / gcd(a,b).

What is Euclidean Algorithm (GCD) Visualizer?

A Euclidean Algorithm Visualizer animates how the GCD of two integers is found by repeatedly replacing the pair (a, b) with (b, a mod b) until b reaches zero — at which point a is the greatest common divisor.

Features

Step-by-step animation

Watch each division-and-remainder step until the remainder hits zero.

Complexity

Time: O(log min(a, b)) division steps. Space: O(1).

100% private

Runs entirely in your browser — nothing is uploaded.

Example

Input

gcd(48, 18)

Output

48 = 2·18 + 12; 18 = 1·12 + 6; 12 = 2·6 + 0 → GCD = 6

Common use cases

  1. 1

    Reduce fractions

    Use the GCD to simplify a fraction to lowest terms.

  2. 2

    Understand the algorithm

    See why remainders shrink quickly, giving logarithmic steps.

  3. 3

    Number theory basics

    Learn the foundation for modular arithmetic and RSA.

Summary

Zerethon's Euclidean algorithm visualizer animates finding the greatest common divisor of two integers in your browser, repeatedly replacing the larger number with the remainder of dividing it by the smaller until the remainder is zero. It runs in O(log min(a, b)) division steps with O(1) space — one of the oldest algorithms still in use (Euclid's Elements, ~300 BC).

Category
Algorithm
Pricing
Free
Privacy
Browser-based
Signup
Not required

References

Privacy

Your data never leaves your browser unless explicitly stated. Euclidean Algorithm (GCD) Visualizer runs entirely client-side — no server upload, no logging, no tracking of your input.

New to this? Read the step-by-step explanation with Big-O analysis: Learn Number Theory →

Compare

LCM vs GCD

Related tools

Bubble Sort Visualizer

Animated bubble sort with step controls, speed, custom input, live comparison/swap counters and pseudocode. Runs entirely in your browser.

Open tool

Insertion Sort Visualizer

Animated insertion sort with step controls, speed, custom input, live comparison/write counters and pseudocode. Runs in your browser.

Open tool

Selection Sort Visualizer

Animated selection sort with step controls, speed, custom input, live comparison/swap counters and pseudocode. Runs in your browser.

Open tool

Merge Sort Visualizer

Animated merge sort with step controls, speed, custom input, live comparison/write counters and pseudocode. Runs in your browser.

Open tool

Build, share, and grow on Zerethon Social

Free signup. Earn points, collect achievements, and connect with creators worldwide.

Sign up free