The Euclidean Algorithm and Long Division

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.

New York State Common Core Math Grade 6, Module 2, Lesson 19

Worksheets for Grade 6

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.

The following diagram gives some examples of how to use the Euclid’s Algorithm to find the GCF. Scroll down the page for more examples and solutions.

 

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
GCF(96, 144)
GCF(660, 840)

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?

• Show Step-by-step Solutions

• Show Step-by-step Solutions

Problem Set

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?

• Show Step-by-step Solutions

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.