Euclidean Algorithm

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)$ by $(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.

The Geometric Picture: Squares in a 48 by 18 Rectangle

A rectangle is $48$ by $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.

The Subtraction Version

Find $\text{GCF}(35, 14)$ using only subtraction: always subtract the smaller number from the larger one.

Subtract 14 from 35: $35 - 14 = 21$ = New pair $(21, 14)$

Subtract 14 again: $21 - 14 = 7$ = New pair $(14, 7)$

Now 7 is smaller: subtract 7: $14 - 7 = 7$ = New pair $(7, 7)$

Subtract once more: $7 - 7 = 0$ = The numbers stop at $7$

Answer: $\text{GCF}(35, 14) = 7$. Subtracting $14$ twice is the same as one division: $35 = 2 \times 14 + 7$. Division is just a shortcut for many subtractions.

A Classic: GCF of 1071 and 462

Find $\text{GCF}(1071, 462)$ with the Euclidean algorithm.

Divide 1071 by 462: $462 \times 2 = 924$ and $1071 - 924 = 147$ = $1071 = 2 \times 462 + 147$

Replace the pair by (462, 147) and divide: $147 \times 3 = 441$ and $462 - 441 = 21$ = $462 = 3 \times 147 + 21$

Replace the pair by (147, 21) and divide: $21 \times 7 = 147$, nothing is left = $147 = 7 \times 21 + 0$

Read the last nonzero remainder: The remainder became $0$ when dividing by $21$ = $\text{GCF}(1071, 462) = 21$

Answer: $\text{GCF}(1071, 462) = 21$. Check: $1071 = 21 \times 51$ and $462 = 21 \times 22$.

Simplifying a Hard Fraction

Simplify $\frac{391}{667}$ to lowest terms.

Divide 667 by 391: $667 = 1 \times 391 + 276$ = Remainder $276$

Divide 391 by 276: $391 = 1 \times 276 + 115$ = Remainder $115$

Divide 276 by 115: $276 = 2 \times 115 + 46$ = Remainder $46$

Divide 115 by 46, then 46 by 23: $115 = 2 \times 46 + 23$ and $46 = 2 \times 23 + 0$ = $\text{GCF}(391, 667) = 23$

Divide top and bottom by 23: $\frac{391 \div 23}{667 \div 23} = \frac{17}{29}$ = $\frac{17}{29}$

Answer: $\frac{391}{667} = \frac{17}{29}$. Since $17$ and $29$ are both prime, the fraction cannot be simplified further.

The LCM from the GCF

Find $\text{LCM}(84, 120)$ using the Euclidean algorithm.

Divide 120 by 84: $120 = 1 \times 84 + 36$ = Remainder $36$

Divide 84 by 36: $84 = 2 \times 36 + 12$ = Remainder $12$

Divide 36 by 12: $36 = 3 \times 12 + 0$ = $\text{GCF}(84, 120) = 12$

Use LCM = a × b ÷ GCF: $\frac{84 \times 120}{12} = \frac{10080}{12}$ = $840$

Check: $840 \div 84 = 10$ and $840 \div 120 = 7$ = Both divide $840$

Answer: $\text{LCM}(84, 120) = 840$.

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.

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

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

Mistake: Giving $0$ or the last quotient as the GCF

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

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

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

Mistake: Taking $a \times b$ as the LCM

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

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.

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.

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.

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

Screen Aspect Ratios

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

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

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

The GCF is the last nonzero remainder, the divisor in the final row

It works because $\text{GCF}(a, b) = \text{GCF}(b, r)$: both pairs have the same common divisors

Geometrically, it cuts an $a \times b$ rectangle into the largest possible squares; the last square side is the GCF

The subtraction version subtracts the smaller number again and again; division is its shortcut

Use 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$)

Q: Does it matter which number I start with?

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

Q: Is the Euclidean algorithm faster than prime factorization?

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

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

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

Q: Can I use it for three numbers?

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

Exit Presentation

Euclidean Algorithm

1 / 14

Number Theory / Factors & Multiples

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.

Advanced25 min

Use arrow keys or spacebar to navigate