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$.

Teacher Resources

Euclidean Algorithm

Q: 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.

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

Advanced25 minLesson

Share to Classroom

Printable worksheet

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.

Try it now

In the Euclidean algorithm you write

a = q \times b + r

with

0 \le r < b

. Which pair do you divide next?

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$ .

Interactive Visual

Largest squares in a rectangle: pick a pair

First numberSecond number

Rectangle 1071 × 462

Press Next step to cut off the biggest squares that fit.

Your turn: type the quotient and the remainder of each row

First numberSecond number

Rectangle 168 × 120

How many times does 120 fit into 168, and what is left over?

168 =× 120 +

Interactive Sandbox

Expression Calculator

Try these:

History

No calculations yet

Practice Problems

18 problems

Problem 1 of 18

Easy

In the Euclidean algorithm you write

a = q \times b + r

with

0 \le r < b

. Which pair do you divide next?

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

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.

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$

Today's challengeOne problem, three tries

Euclidean Algorithm

Definition

Worked Examples

Common Mistakes

Interactive Visual

Interactive Sandbox

Expression Calculator

History

Practice Problems

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)