The Euclidean Algorithm and Long Division
Video Solutions to help Grade 6 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.
Plans and Worksheets for Grade 6
Plans and Worksheets for all Grades
Lessons for Grade 6
Common Core For Grade 6
New York State Common Core Math Module 2, Grade 6, Lesson 19
NYS Math Module 2 Grade 6 Lesson 19 Classwork
Euclid’s Algorithm is used to find the greatest common factor (GCF) of two whole numbers.
1. Divide the larger of the two numbers by the smaller one.
2. If there is a remainder, divide it into the divisor.
3. Continue dividing the last divisor by the last remainder until the remainder is zero.
4. The final divisor is the GCF of the original 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 so that there is no overlap or gaps.
Example 1: Euclid’s Algorithm Conceptualized
What is the GCF of 60 and 100?
Example 2: Lesson 18 Classwork Revisited
a. Let’s apply Euclid’s Algorithm to some of the problems from our last lesson.
i. What is the GCF of 30 and 50?
Example 3: Larger Numbers
Example 4: Area Problems
The greatest common factor has many uses. Among them, the GCF lets us find out the maximum size of squares that will
cover a rectangle. Whenever we solve problems like this, we cannot have any gaps or any overlapping squares. Of
course, the maximum size squares will be the minimum number of squares needed.
A rectangular computer table measures 30 inches by 50 inches. We need to cover it with square tiles. What is the side
length of the largest square tile we can use to completely cover the table, so that there is no overlap or gaps?