Euclidean Algorithm Facts For Kids
The Euclidean algorithm is a method for finding the greatest common divisor of two integers through a series of division steps.
About this topic
Key Points
Photos of Euclidean Algorithm
A 24×60 rectangle is covered with ten 12×12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a×b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b.
Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.
The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.
Plot of a linear Diophantine equation, 9x + 12y = 483. The solutions are shown as blue circles.
The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4
Number of steps in the Euclidean algorithm for gcd(x,y). Lighter (red and yellow) points indicate relatively few steps, whereas darker (violet and blue) points indicate more steps. The largest dark area follows the line y = Φx, where Φ is the golden ratio.
Distribution of Gaussian primes u + vi in the complex plane, with norms u2 + v2 less than 500
Distribution of Eisenstein primes u + vω in the complex plane, with norms less than 500. The number ω is a cube root of 1.