Teacher Guide: Euclidean Algorithm

Find the greatest common factor of any two numbers by repeated division with remainder, and use it to simplify fractions and find the LCM.

Present Lesson Share to Classroom View Student Page

Use this lesson with your class

Free, no student accounts needed.

Share with students

Students open the lesson and practise with instant feedback.

Printable worksheet

All practice problems on paper, with a separate answer key.

Worksheet Answer key

Class quiz

10 questions on Factors & Multiples. Students join with a name, you see everyone's score.

For Teachers

Learning Objectives

Write a division with remainder in the form $a = q \times b + r$ with $0 \le r < b$
Find the GCF of two numbers with the Euclidean algorithm and with its subtraction version
Explain why $\text{GCF}(a, b) = \text{GCF}(b, r)$ and connect the algorithm to cutting a rectangle into squares
Use the GCF to simplify fractions and to compute $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$
Decide whether two numbers are coprime and compare the algorithm with prime factorization

Prerequisites

• Greatest Common Factor (GCF): finding it by listing factors and by prime factorization
• Least Common Multiple (LCM) and its meaning
• Prime factorization and prime and composite numbers
• Division of whole numbers with a remainder

Discussion Starters

1. Why must the algorithm always stop? What happens to the numbers at each step?
2. If $d$ divides $48$ and $18$ , why must it also divide $48 - 2 \times 18 = 12$ ?
3. When would you rather use prime factorization, and when the Euclidean algorithm?
4. Why do neighboring Fibonacci numbers like $144$ and $89$ need so many steps?
5. How does cutting a rectangle into squares show the same steps as the divisions?

Common Misconceptions

The GCF is the last number written down, which is often the remainder $0$ or a quotient

Remediation: Label each row with q and r in different colors. Circle the divisor of the row whose remainder is $0$ and check that it divides both original numbers.

After the first division you continue with the original larger number

Remediation: Use the rectangle picture: once the squares are cut off, the large side is gone and only the leftover rectangle (b by r) remains.

The algorithm is a trick that happens to work

Remediation: Show with $48$ , $18$ , $12$ that every common divisor of $48$ and $18$ divides $12$ , and every common divisor of $18$ and $12$ divides $48$ . List both sets of common divisors: they are equal.

Differentiation Ideas

For Struggling Students:

• Start with the subtraction version on small pairs like (35, 14) before using division
• Use grid paper rectangles and cut off squares physically
• Provide a table with columns a, b, q, r to fill in row by row

For On-Level Students:

• Run the algorithm on three- and four-digit pairs like (1071, 462)
• Simplify fractions like $\frac{391}{667}$ with the GCF
• Find LCMs with $\frac{a \times b}{\text{GCF}(a, b)}$ and check them

For Advanced Students:

• Prove that $\text{GCF}(a, b) = \text{GCF}(b, r)$ in general
• Investigate why neighboring Fibonacci numbers give the most steps
• Explore the extended Euclidean algorithm: write $\text{GCF}(a, b)$ as $x \times a + y \times b$

Standards Alignment

6.NS.B.4 (CCSS.MATH.CONTENT.6.NS.B.4)
Find the greatest common factor of two whole numbers and the least common multiple of two whole numbers
6.NS.B.2 (CCSS.MATH.CONTENT.6.NS.B.2)
Fluently divide multi-digit numbers using the standard algorithm
MP.7 (CCSS.MATH.PRACTICE.MP7)
Look for and make use of structure

Lesson Resources

visualRectangle into Squares
Interactive view that cuts an a by b rectangle into the largest squares while writing each row a = q × b + r
activityGrid Paper Squares
Students draw a 48 by 18 rectangle on grid paper and cut off the largest squares with scissors until only equal squares remain
gameGCF Race
One team uses prime factorization, the other the Euclidean algorithm, on pairs like (1071, 462) and (391, 667)
worksheetEuclid Rows Practice
Fill in quotients and remainders, then simplify fractions and find LCMs from the GCF

Lesson Content

Everything students see: definition, examples, common mistakes, applications. Tap to open.

Definition

The Euclidean algorithm is a fast way to find the greatest common factor (GCF) of two whole numbers without listing factors or building factor trees.

Divide the larger number

a

by the smaller number

b

and write the result as a division with remainder:

a = q \times b + r, \quad 0 \le r < b

Here

q

is the quotient and

r

is the remainder. Then **replace the pair

(a, b)

(b, r)

** and divide again. Repeat until the remainder is

0

. The last nonzero remainder (the divisor in the final row) is the GCF.

Example:

\text{GCF}(48, 18)

$48 = 2 \times 18 + 12$
$18 = 1 \times 12 + 6$
$12 = 2 \times 6 + 0$

The remainder is

0

, so

\text{GCF}(48, 18) = 6

Why it works: if a number

d

divides both

a

and

b

, it also divides

r = a - q \times b

. And if

d

divides both

b

and

r

, it also divides

a = q \times b + r

. So the pairs

(a, b)

and

(b, r)

have exactly the same common divisors, and therefore the same GCF:

\text{GCF}(a, b) = \text{GCF}(b, r)

The numbers get smaller at every step, so the algorithm always stops.

Worked Examples

A rectangle is

48

18

. Cut off the largest squares you can, again and again. What is the side of the squares that finally fit exactly?

Cut squares of side 18 from the long side

Two

18 \times 18

squares fit,

12

is left over:

48 = 2 \times 18 + 12

→ Leftover rectangle

18 \times 12

Cut squares of side 12 from the leftover

One

12 \times 12

square fits,

6

is left over:

18 = 1 \times 12 + 6

→ Leftover rectangle

12 \times 6

Cut squares of side 6

Two

6 \times 6

squares fit exactly:

12 = 2 \times 6 + 0

→ Nothing is left over

Tile the whole rectangle with the last square

6

divides

48

and

18

\frac{48}{6} \times \frac{18}{6} = 8 \times 3

→

24

squares of side

6

cover it

Answer: The squares of side $6$ fit exactly, so $\text{GCF}(48, 18) = 6$ . Each cut is one row of the algorithm.

Common Mistakes

Keeping the old large number: after $48 = 2 \times 18 + 12$ , continuing with $48$ and $12$

Why it's wrong: The algorithm works because $\text{GCF}(a, b) = \text{GCF}(b, r)$ . The number $a$ is no longer needed after the first division.

Correct: The next pair is $(18, 12)$ : the old divisor and the remainder. So $18 = 1 \times 12 + 6$ .

Giving $0$ or the last quotient as the GCF

Why it's wrong: The last row has remainder $0$ , which only tells you to stop. The quotient counts how many squares fit, it is not a common factor.

Correct: The GCF is the last nonzero remainder, the divisor in the final row. In $12 = 2 \times 6 + 0$ it is $6$ .

Writing a remainder that is too big, like $1071 = 1 \times 462 + 609$

Why it's wrong: The equation is true, but $609 > 462$ , so $462$ still fits into it. The remainder must be smaller than the divisor.

Correct: Take the largest quotient possible: $1071 = 2 \times 462 + 147$ with $147 < 462$ .

Taking $a \times b$ as the LCM

Why it's wrong: $a \times b$ is always a common multiple, but usually not the least one: $84 \times 120 = 10080$ counts the common factor $12$ twice.

Correct: Divide by the GCF: $\text{LCM}(84, 120) = \frac{84 \times 120}{12} = 840$ .

Why It Matters

The Euclidean algorithm is more than 2,300 years old (Euclid wrote it down around 300 BC) and it is still one of the most used algorithms in the world:

Big numbers: factoring $1071$ or $391$ into primes is slow, but three or four divisions give the GCF right away. For numbers with hundreds of digits, prime factorization is practically impossible, while the Euclidean algorithm still finishes in at most a few thousand quick steps.
Fractions: to simplify $\frac{391}{667}$ you need $\text{GCF}(391, 667) = 23$ , which is hard to see by factoring but quick with the algorithm.
LCM: once you know the GCF, $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$ , so one algorithm gives both.
Tiles, gears and screens: the largest square tile for a floor, when two gears line up again, and why a $1920 \times 1080$ screen is $16:9$ all come down to the GCF.
Internet security: encryption systems like RSA use an extended version of this algorithm every time you open a secure website.

Real World Applications

Tiling a Floor with the Largest Square Tiles

A tiler wants to cover a rectangular floor with equal square tiles without cutting any. The largest possible tile side is the GCF of the two lengths.

Example:

A $48$ cm by $18$ cm panel is covered exactly by $6$ cm squares: $\text{GCF}(48, 18) = 6$ , so $8 \times 3 = 24$ tiles.

1Try It Yourself

A hallway floor is $168$ cm by $120$ cm. It must be covered with equal square tiles, with no cutting and no gaps.

What is the side of the largest square tile that works, in cm?

Step 1: Write the mathematical expression

Find $\text{GCF}(168, 120)$ with the Euclidean algorithm:

Gears and Repeating Cycles

When two gears turn together, the same pair of teeth meets again after a number of teeth equal to the LCM of the tooth counts. The Euclidean algorithm gives the GCF, and the LCM follows.

Example:

Gears with $18$ and $48$ teeth: $\text{GCF} = 6$ , so the same teeth meet again after $\frac{18 \times 48}{6} = 144$ teeth.

2Try It Yourself

A bicycle gear has $84$ teeth and a small gear has $36$ teeth. Two marked teeth touch now.

After how many teeth have passed do the two marked teeth touch again?

Step 1: Write the mathematical expression

Find $\text{LCM}(84, 36) = \frac{84 \times 36}{\text{GCF}(84, 36)}$ :

Screen Aspect Ratios

A screen resolution like $1920 \times 1080$ is turned into an aspect ratio by dividing both numbers by their GCF.

Example:

$1280 \times 1024$ : $\text{GCF}(1280, 1024) = 256$ , so the ratio is $5:4$ .

3Try It Yourself

A monitor has $1920$ by $1080$ pixels. To write its aspect ratio, you divide both numbers by their GCF.

What is $\text{GCF}(1920, 1080)$ ?

Step 1: Write the mathematical expression

Run the Euclidean algorithm on $1920$ and $1080$ :

Key Takeaways

1Euclidean algorithm: divide $a$ by $b$ as $a = q \times b + r$ with $0 \le r < b$ , then replace $(a, b)$ by $(b, r)$ until the remainder is $0$
2The GCF is the last nonzero remainder, the divisor in the final row
3It works because $\text{GCF}(a, b) = \text{GCF}(b, r)$ : both pairs have the same common divisors
4Geometrically, it cuts an $a \times b$ rectangle into the largest possible squares; the last square side is the GCF
5The subtraction version subtracts the smaller number again and again; division is its shortcut
6Use it to simplify fractions, to find $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$ , and to test if two numbers are coprime (GCF $= 1$ )

Frequently Asked Questions

Does it matter which number I start with?

No. If you start with the smaller number on top, the first row is like

18 = 0 \times 48 + 18

, which just swaps the two numbers. Starting with the larger one saves that step.

Is the Euclidean algorithm faster than prime factorization?

For small numbers like

12

and

18

both are quick. For large numbers, yes, by far: you never need to find a single prime.

\text{GCF}(1071, 462)

takes three divisions, while factoring needs

1071 = 3^2 \times 7 \times 17

and

462 = 2 \times 3 \times 7 \times 11

What does it mean if the algorithm ends with GCF 1?

Then the two numbers are coprime (relatively prime): they share no factor except

1

. Neighboring Fibonacci numbers like

144

and

89

are always coprime, and they make the algorithm take the most steps for their size.

Can I use it for three numbers?

Yes, two at a time:

\text{GCF}(a, b, c) = \text{GCF}(\text{GCF}(a, b), c)

. For example,

\text{GCF}(840, 1176) = 168

and

\text{GCF}(168, 1260) = 84

, so the GCF of all three is

84

Glossary

Euclidean algorithm: A method for the GCF of two numbers: divide with remainder, replace the pair by (divisor, remainder), repeat until the remainder is $0$
Division with remainder: Writing $a = q \times b + r$ with $0 \le r < b$ , for example $1071 = 2 \times 462 + 147$
Quotient: The number $q$ of whole times $b$ fits into $a$
Remainder: The number $r$ left over after division, always smaller than the divisor
Coprime (relatively prime): Two numbers whose GCF is $1$ , like $144$ and $89$
Least common multiple (LCM): The smallest positive number that both numbers divide; $\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}$

Formula Card

Division with remainder

a = q \times b + r, \quad 0 \le r < b

One row of the algorithm: $q$ is the quotient, $r$ the remainder

Key step

\text{GCF}(a, b) = \text{GCF}(b, r)

Replace the pair by (divisor, remainder) and repeat until $r = 0$

LCM from the GCF

\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}

Multiply the numbers and divide by their GCF

Coprime numbers

\text{GCF}(a, b) = 1

The numbers share no factor except $1$

Teacher Guide: Euclidean Algorithm

Use this lesson with your class

For Teachers

For Struggling Students:

For On-Level Students:

For Advanced Students:

Lesson Content

Definition

Worked Examples

Common Mistakes

Why It Matters

Real World Applications

Tiling a Floor with the Largest Square Tiles

Gears and Repeating Cycles

Screen Aspect Ratios

Key Takeaways

Frequently Asked Questions

Glossary

Formula Card

Division with remainder

Key step

LCM from the GCF

Coprime numbers

More in This Topic

Factors and Multiples

Prime Factorization

Prime and Composite Numbers

Greatest Common Factor (GCF)