Euclidean Algorithm Visualizer
Find the greatest common divisor of two numbers with the Euclidean algorithm, showing each division step and the extended Bezout coefficients.
Last reviewed by the Radiatus Cloud team
Compute the greatest common divisor step by step with the Euclidean algorithm.
Need this done properly for your business?
Radiatus delivers secure cloud, DevOps & compliance engineering.
Compute GCD with the Euclidean algorithm
The Euclidean algorithm is an ancient and highly efficient method for finding the greatest common divisor of two numbers. It works by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder is zero; the last non-zero remainder is the greatest common divisor. This visualizer shows each division step so you can follow exactly how the algorithm narrows down to the answer, and it also gives the least common multiple. For forty-eight and thirty-six, the greatest common divisor is twelve.
Seeing the steps makes clear why the method is so fast: each step shrinks the numbers quickly.
An algorithm from antiquity
Described by Euclid over two thousand years ago, this algorithm remains one of the most elegant and important in mathematics and computing, underpinning everything from simplifying fractions to modern cryptography. Its efficiency comes from using remainders rather than repeatedly subtracting, so even very large numbers are handled in few steps. The greatest common divisor and least common multiple are linked, since their product equals the product of the two original numbers.
Understanding the steps builds intuition for modular arithmetic, which the algorithm extends into. All calculation happens locally in your browser.
Related tools
- Data Collection Analysis — Analyze app description to infer data collection.
- Dark Pattern Detector — Scan UX text for manipulative patterns.
- AI Risk Disclosure — Generate disclosure text for AI features.
- Maturity Radar — Generate a radar chart of security maturity.
Frequently Asked Questions
How does the Euclidean algorithm work?
It repeatedly replaces the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero remainder is the GCD.
Why is it so efficient?
Using remainders shrinks the numbers rapidly, so even very large inputs reach the answer in relatively few steps compared with subtraction.
How is the LCM related to the GCD?
The product of two numbers equals the product of their GCD and LCM, so the LCM is the product divided by the GCD.
Where is the algorithm used?
In simplifying fractions, modular arithmetic and cryptography, making it one of the most widely used algorithms in mathematics and computing.
Privacy & Security
Everything runs in your browser; nothing is uploaded.
How to Use
Enter two positive integers to see the GCD computed step by step.
Disclaimer: This tool is provided "as is" without warranty of any kind. Results are for educational and utility purposes.