The Euclidean Algorithm
Initializing live version
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
A graphical interpretation of Euclid's algorithm for calculating the greatest common divisor of two numbers: Given numbers 
and 
, draw a rectangle with width and height . If this rectangle is divided into squares as shown in the Demonstration, then the width of the smallest square (shown in red) is the greatest common divisor of and .
Contributed by: Matthew Szudzik (March 2011)
Suggested by: Stephen Wolfram
Open content licensed under CC BY-NC-SA
Snapshots
Details
Permanent Citation
Related Demonstrations
More by Author
Euclidean Algorithm Steps
Michael Trott
Extended Euclidean Algorithm
?tefan Porubský
The Euclidean Algorithm and Simple Continued Fractions
?tefan Porubský
Solving a Linear Diophantine Equation in Two Variables by the Euclidean Algorithm
Izidor Hafner
Proposition 30, Book XI, Euclid's Elements
Izidor Hafner
Platonic Solids
Stephen Wolfram and Eric W. Weisstein
Finding the Least Common Multiple of Two Numbers by Factoring
Jesse Nochella
Finding the Greatest Common Divisor of Two Numbers by Factoring
Jesse Nochella
Recursive Extended Euclidean Algorithm
Roger B. Kirchner
Primitive Pythagorean Triples 1: Scatter Plot
Robert L. Brown
