Greatest Common Divisor by Euclid’s Algorithm

Goal

Find the greatest common divisor (GCD) using Euclid’s algorithm, then give the final answer in simplest form.

Core idea

Euclid’s algorithm uses repeated division with remainder:

1. Divide the larger number by the smaller one.
2. Write the remainder.
3. Replace the pair with the smaller number and the remainder.
4. Repeat until the remainder is 0.
5. The last nonzero remainder is the GCD.

Method

1. Start with the two given integers.
2. Keep dividing and recording remainders.
3. Continue until you reach a remainder of 0.
4. Read the GCD from the last nonzero remainder.
5. If the exercise asks for a simplified final answer, make sure your result is written in its simplest exact form.

Check

• The GCD must divide both original numbers exactly.
• If you divide either number by your answer, the remainder should be 0.
• You can also verify by listing common divisors for a quick sanity check, but Euclid’s algorithm is the main method.

Common caution

Do not stop at the first remainder. Keep going until the remainder becomes 0, because the final nonzero remainder is the one that matters.