# Euclid's Algorithm on a Pool Table

Author:
dborkovitz
This applet shows a visual illustration of Euclid's Algorithm on a pool table, where after each bounce of the ball, a square is removed from the table. When the remaining table is square, the side of that square is the GCD. Press next for the ball to travel to the next wall. Move the sliders to change the dimensions of the rectangle (pressing reset or not). Euclid's Algorithm is a way to find the greatest common divisor of two natural numbers by repeated subtraction (division can also be used to group repeated subtractions together). For example, to use Euclid's Algorithm to find GCD(51,21): 51-21=30 30-21=9 21-9=12 12-9=3 9-3=6 6-3=3 (since 3 is the last non-zero difference, it is the GCD) 3-3=0
How does the pool table picture connect to Euclid's algorithm? Try doing the algorithm with paper and pencil for an example. When is the path of the ball a spiral? Find two or more rectangles where the path of the ball is the same shape, even though the rectangles are different sizes. Generalize. Why does Euclid's algorithm work?