Videos and 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 Grade 6, Module 2, 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?
1. Use Euclid’s algorithm to find the greatest common factor of the following pairs of numbers:
a. GCF (12,78)
b. GCF (18,176)
2. Juanita and Samuel are planning a pizza party. They order a rectangular sheet pizza that measures 21 inches by
36 inches. They tell the pizza maker not to cut it because they want to cut it themselves.
a. All pieces of pizza must be square with none left over. What is the side length of the largest square pieces into which Juanita and Samuel can cut the pizza?
b. How many pieces of this size can be cut?
3. Shelly and Mickelle are making a quilt. They have a piece of fabric that measures 48 inches by 168 inches.
a. All pieces of fabric must be square with none left over. What is the side length of the largest square pieces into which Shelly and Mickelle can cut the fabric?
b. How many pieces of this size can Shelly and Mickelle cut?
Try the free Mathway calculator and
problem solver below to practice various math topics. Try the given examples, or type in your own
problem and check your answer with the step-by-step explanations.
We welcome your feedback, comments and questions about this site or page. Please submit your feedback or enquiries via our Feedback page.