Visualizing the Euclidean Algorithm
The Euclidean Algorithm is used to the find the GCD of two integers, a and b. The form of the Euclidean Algorithm is as follows where q and r are integers as well:
Assume a is greater than b or switch the roles:
a= q0*b + r0, b>r0>0 b= q1*r0 + r1, r0>r1>0 r0= q2*r1+r2, r1>r2>0 r1= q3*r2+r3, r2>r3>0 . . rn-1=qn+1*rn +0
1) Move the point to choose integers a and b. 2) Now move the slider to stage 2. You will notice that a square has been eliminated from the initial rectangle, and the result is yet another rectangle. Converse with a partner: What does the square that was eliminated represent? Suppose more than one of the same-sized square is eliminated. What does this represent? 3) Continue to move the slider until you can no longer eliminate same-sized squares. The stage at which this occurs depends on the integers you chose. 4) Now move the slider one more stage. You may have noticed that the elimination of squares has switched directions. If they were being eliminated horizontally, then they are now being eliminated vertically and vice versa. Converse with a partner. Why does this happen? Make a conjecture. 5) Move the slider until all possible squares have been eliminated. Converse with a partner. Conjecture why the last square is the GCD(a,b). Be prepared to share your conjectures with the class.