Find GCD using the Euclidean algorithm with visual rectangle decomposition. Shows extended GCD and Bezout coefficients.
The Euclidean Algorithm Visualizer takes two integers and runs the repeated-division process from Euclid's Elements: divide, keep the remainder, repeat, and the last nonzero remainder is the greatest common divisor (GCD). Each step is drawn as squares filling a rectangle of the two inputs, so the GCD appears as the largest square that tiles it exactly. An extended run also returns Bezout coefficients x and y with ax + by = gcd(a,b). What surprises people: the GCD is not the product of common prime factors you would spot by inspection. The process is purely mechanical, works for any pair, and the Bezout identity is a byproduct of the same steps.
A concrete input and expected output from the current implementation.
Input
252 and 105
Expected output
GCD: 21 Steps: 252 = 2 x 105 + 42 105 = 2 x 42 + 21 42 = 2 x 21 + 0 Bezout identity: 21 = -2 x 252 + 5 x 105
21 is the last nonzero remainder, so it is the GCD. Back-substituting the remainders rewrites 21 as -2(252) + 5(105), and -504 + 525 = 21 verifies the Bezout identity.
Divide the larger input by the smaller and record the quotient and remainder. Replace the pair with (smaller, remainder) and repeat until the remainder is 0; the last nonzero remainder is the GCD. Each quotient counts how many squares of that step's size fit across the current rectangle, so the animation mirrors the arithmetic. Termination is fast: the numbers shrink by about half every two steps.
The extended pass threads two auxiliary coefficient pairs through the same division steps so the final line reads ax + by = gcd(a,b). These coefficients are not unique: with g = gcd(a,b), adding (b/g, -a/g) to (x, y) yields another valid pair, so the tool shows one representative, usually the smallest in absolute value. It underlies modular inverses and the integer solutions of ax + by = c.
The GCD is the side length of the largest square that tiles an a-by-b rectangle exactly. Each step of the algorithm cuts the largest possible square out of the current region, and the square size that finally leaves no leftover is the GCD. The counts per step are exactly the division quotients, so the picture and the arithmetic tell the same story.
Not as a dedicated operation, but the Bezout output is exactly what you need. When gcd(a,m) = 1 the identity reads ax + my = 1, so x reduced modulo m is a's inverse; when gcd(a,m) > 1 no inverse exists and no coefficient pair changes that. Reduce x into the range 0 to m-1 yourself.
The example and behavioral notes were checked against the browser implementation. Standards and primary references below define the relevant format, formula, or platform behavior.
Calculate percentages, percentage change, and what percent one number is of another with step-by-step breakdowns.
Calculate tips and split bills between multiple people with customizable tip percentages and rounding options.
Calculate monthly payments, total interest, and generate amortization schedules for loans and mortgages.
Calculate Body Mass Index from height and weight with category classification and healthy range guidance.
Calculate sale prices, savings amounts, and final costs after single or stacked percentage discounts.
Compute mean, median, mode, standard deviation, variance, and other descriptive statistics from a data set.