Number theory / Euclid's algorithm
One division.
A smaller remainder.
Follow the common divisor through each step. Then see how the answer can be built from an integer combination of the two numbers you started with.
Choose two integers, then compute their division steps.
the next dividend.The remainder becomes the next divisor.
Repeat until that divisor is zero.
Complete computed result
Greatest common divisor
For (0, 0), this explorer uses gcd(0, 0) = 0. This is a convention, not a greatest positive divisor of zero.
No division is needed
The initial second entry is already zero. The algorithm stops at the original pair and returns its first entry.
Blue groups the complete multiple; gold is the remainder. Strip widths show approximate relative sizes. Exact values are written above, including remainders too small to see at this scale.
Check the integer combinations
Each row still uses the original A and B. Subtracting q copies of the divisor's coefficients gives the remainder's coefficients.
- Dividend
- Divisor
- Remainder
| Step | Dividend | Divisor | q | r |
|---|
The JSON contains the original integer values, every division and its coefficients, and the terminal result. It uses decimal text for exact integers.
Why the answer survives
Keep the common divisors.
If A = qB + r, a number that divides A and B also divides r. A number that divides B and r also divides A. Both pairs therefore have the same common divisors.
Every new remainder lies from zero up to—but excluding—the divisor. That shrinking nonnegative integer guarantees a stopping point.
Study the connections
A twelve-question lesson.
Practice division, the stopping rule, common-divisor problems and integer combinations. Each question includes a worked explanation and a new problem to try.
In RecallWeave, choose Bring your own lesson, select the JSON and review it before choosing Start this deck. This page's trace is a worked calculation; the lesson file is a separate download.