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 min18 problems
Practice Problems

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.

Try it now

In the Euclidean algorithm you write a=q×b+ra = q \times b + r with 0≤r<b0 \le r < b. Which pair do you divide next?

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.

Interactive Visual

Largest squares in a rectangle: pick a pair

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

    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×b+ra = q \times b + r with 0≤r<b0 \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 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

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

      Today's challengeOne problem, three tries

      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