Back to Lesson

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 LessonShare to ClassroomView 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×b+ra = q \times b + r with 0≤r<b0 \le r < b
  • Find the GCF of two numbers with the Euclidean algorithm and with its subtraction version
  • Explain why GCF(a,b)=GCF(b,r)\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 LCM(a,b)=a×bGCF(a,b)\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 dd divides 4848 and 1818, why must it also divide 48−2×18=1248 - 2 \times 18 = 12?
  • 3. When would you rather use prime factorization, and when the Euclidean algorithm?
  • 4. Why do neighboring Fibonacci numbers like 144144 and 8989 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 00 or a quotient

Remediation: Label each row with q and r in different colors. Circle the divisor of the row whose remainder is 00 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 4848, 1818, 1212 that every common divisor of 4848 and 1818 divides 1212, and every common divisor of 1818 and 1212 divides 4848. 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 391667\frac{391}{667} with the GCF
  • • Find LCMs with a×bGCF(a,b)\frac{a \times b}{\text{GCF}(a, b)} and check them

For Advanced Students:

  • • Prove that GCF(a,b)=GCF(b,r)\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 GCF(a,b)\text{GCF}(a, b) as x×a+y×bx \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 aa by the smaller number bb and write the result as a division with remainder:
a=q×b+r,0≤r<ba = q \times b + r, \quad 0 \le r < b
Here qq is the quotient and rr is the remainder. Then **replace the pair (a,b)(a, b) by (b,r)(b, r)** and divide again. Repeat until the remainder is 00. The last nonzero remainder (the divisor in the final row) is the GCF.
Example: GCF(48,18)\text{GCF}(48, 18)
  • 48=2×18+1248 = 2 \times 18 + 12
  • 18=1×12+618 = 1 \times 12 + 6
  • 12=2×6+012 = 2 \times 6 + 0
The remainder is 00, so GCF(48,18)=6\text{GCF}(48, 18) = 6.
Why it works: if a number dd divides both aa and bb, it also divides r=a−q×br = a - q \times b. And if dd divides both bb and rr, it also divides a=q×b+ra = q \times b + r. So the pairs (a,b)(a, b) and (b,r)(b, r) have exactly the same common divisors, and therefore the same GCF:
GCF(a,b)=GCF(b,r)\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 4848 by 1818. Cut off the largest squares you can, again and again. What is the side of the squares that finally fit exactly?
1

Cut squares of side 18 from the long side

Two 18×1818 \times 18 squares fit, 1212 is left over: 48=2×18+1248 = 2 \times 18 + 12 → Leftover rectangle 18×1218 \times 12
2

Cut squares of side 12 from the leftover

One 12×1212 \times 12 square fits, 66 is left over: 18=1×12+618 = 1 \times 12 + 6 → Leftover rectangle 12×612 \times 6
3

Cut squares of side 6

Two 6×66 \times 6 squares fit exactly: 12=2×6+012 = 2 \times 6 + 0 → Nothing is left over
4

Tile the whole rectangle with the last square

66 divides 4848 and 1818: 486×186=8×3\frac{48}{6} \times \frac{18}{6} = 8 \times 3 → 2424 squares of side 66 cover it

Common Mistakes

Keeping the old large number: after 48=2×18+1248 = 2 \times 18 + 12, continuing with 4848 and 1212

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

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

Giving 00 or the last quotient as the GCF

Why it's wrong: The last row has remainder 00, 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×6+012 = 2 \times 6 + 0 it is 66.

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

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

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

Taking a×ba \times b as the LCM

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

Correct: Divide by the GCF: LCM(84,120)=84×12012=840\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 10711071 or 391391 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 391667\frac{391}{667} you need GCF(391,667)=23\text{GCF}(391, 667) = 23, which is hard to see by factoring but quick with the algorithm.
  • LCM: once you know the GCF, LCM(a,b)=a×bGCF(a,b)\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×10801920 \times 1080 screen is 16:916: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 4848 cm by 1818 cm panel is covered exactly by 66 cm squares: GCF(48,18)=6\text{GCF}(48, 18) = 6, so 8×3=248 \times 3 = 24 tiles.

1Try It Yourself

A hallway floor is 168168 cm by 120120 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 GCF(168,120)\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 1818 and 4848 teeth: GCF=6\text{GCF} = 6, so the same teeth meet again after 18×486=144\frac{18 \times 48}{6} = 144 teeth.

2Try It Yourself

A bicycle gear has 8484 teeth and a small gear has 3636 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 LCM(84,36)=84×36GCF(84,36)\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×10241280 \times 1024: GCF(1280,1024)=256\text{GCF}(1280, 1024) = 256, so the ratio is 5:45:4.

3Try It Yourself

A monitor has 19201920 by 10801080 pixels. To write its aspect ratio, you divide both numbers by their GCF.

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

Step 1: Write the mathematical expression

Run the Euclidean algorithm on 19201920 and 10801080:

Key Takeaways

  • 1Euclidean algorithm: divide aa by bb as a=q×b+ra = q \times b + r with 0≤r<b0 \le r < b, then replace (a,b)(a, b) by (b,r)(b, r) until the remainder is 00
  • 2The GCF is the last nonzero remainder, the divisor in the final row
  • 3It works because GCF(a,b)=GCF(b,r)\text{GCF}(a, b) = \text{GCF}(b, r): both pairs have the same common divisors
  • 4Geometrically, it cuts an a×ba \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 LCM(a,b)=a×bGCF(a,b)\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}, and to test if two numbers are coprime (GCF =1= 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×48+1818 = 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 1212 and 1818 both are quick. For large numbers, yes, by far: you never need to find a single prime. GCF(1071,462)\text{GCF}(1071, 462) takes three divisions, while factoring needs 1071=32×7×171071 = 3^2 \times 7 \times 17 and 462=2×3×7×11462 = 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 11. Neighboring Fibonacci numbers like 144144 and 8989 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: GCF(a,b,c)=GCF(GCF(a,b),c)\text{GCF}(a, b, c) = \text{GCF}(\text{GCF}(a, b), c). For example, GCF(840,1176)=168\text{GCF}(840, 1176) = 168 and GCF(168,1260)=84\text{GCF}(168, 1260) = 84, so the GCF of all three is 8484.

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 00
Division with remainder
Writing a=q×b+ra = q \times b + r with 0≤r<b0 \le r < b, for example 1071=2×462+1471071 = 2 \times 462 + 147
Quotient
The number qq of whole times bb fits into aa
Remainder
The number rr left over after division, always smaller than the divisor
Coprime (relatively prime)
Two numbers whose GCF is 11, like 144144 and 8989
Least common multiple (LCM)
The smallest positive number that both numbers divide; LCM(a,b)=a×bGCF(a,b)\text{LCM}(a, b) = \frac{a \times b}{\text{GCF}(a, b)}

Formula Card

Division with remainder

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

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

Key step

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

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

LCM from the GCF

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

Multiply the numbers and divide by their GCF

Coprime numbers

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

The numbers share no factor except $1$

More in This Topic

Factors and Multiples

Elementary20 min

Prime Factorization

Intermediate25 min

Prime and Composite Numbers

Elementary20 min

Greatest Common Factor (GCF)

Intermediate25 min