Unit 2, Lesson 19# The Euclidean Algorithm as an Application of the Long Division Algorithm

EngageNY 45 min(s)

Students explore and discover that Euclid's algorithm is a more efficient means to finding the greatest common factor of larger numbers and determine that Euclid's algorithm is based on long division. Students look for and make use of structure, connecting long division to Euclid's algorithm. Students look for and express regularity in repeated calculations leading to finding the greatest common factor of a pair of numbers. In application, the algorithm can be used to find the side length of the largest square that can be used to completely fill a rectangle without overlap or gaps.