Euclidean Algorithm: How to Find the Greatest Common Divisor

What Is Euclidean Algorithm?

The Euclidean algorithm is a famous mathematical method used to find the greatest common divisor (GCD) or greatest common factor (GCF) of two integers. It is also known as Euclid's algorithm or the Euclidean GCD algorithm.

The method is based on a simple principle: the greatest common divisor of two numbers also divides their difference. This means we can replace a large pair of numbers with a much smaller pair without changing the GCD.

By continually dividing the numbers and keeping only the remainder, we avoid having to list out all the factors manually. The last non-zero remainder in the sequence is the greatest common divisor.

When to Use It

The Euclidean algorithm is extremely useful when dealing with very large numbers. For small numbers, it is often easy to guess the GCD or list the factors. However, finding the prime factorization of large numbers using the fundamental theorem of arithmetic can be incredibly time-consuming.

This algorithm is the most efficient way to simplify fractions with large numerators and denominators. It is also the standard method used to check if two numbers are coprime numbers, meaning their GCD is exactly $1$. Number theorists also use the algorithm in advanced proofs, including those related to prime factorization and perfect numbers.

Step-by-Step Method

To perform the Euclidean algorithm, you will use the standard division equation: $\text{Dividend} = \text{Divisor} \times \text{Quotient} + \text{Remainder}$.

1. Identify the larger of your two numbers as the Dividend and the smaller as the Divisor.
2. Divide the Dividend by the Divisor to find the Quotient and the Remainder.
3. Shift the numbers for the next round: the old Divisor becomes the new Dividend, and the old Remainder becomes the new Divisor.
4. Divide this new pair to find the next Remainder.
5. Repeat this shifting and dividing process until the Remainder is exactly zero.
6. The final non-zero Remainder before you reached zero is the greatest common divisor.

Visual Worked Examples

The algorithm works exactly the same whether you use small or large numbers. Writing the steps out as equations or organizing them into a table helps prevent calculation errors.

Example 1: Equation form

Question: What is the greatest common divisor of $252$ and $105$?

Method:

1. Set up the first division: $252 = 105 \times 2 + 42$.
2. Shift the numbers. Divide $105$ by the remainder $42$: $105 = 42 \times 2 + 21$.
3. Shift the numbers again. Divide $42$ by the remainder $21$: $42 = 21 \times 2 + 0$.
4. The remainder is now $0$. The algorithm stops. The GCD is the previous non-zero remainder, which is $21$.

Answer: The GCD is $21$.

Check: Divide both numbers by $21$. $252 \div 21 = 12$ and $105 \div 21 = 5$. Since $12$ and $5$ share no common factors, $21$ is indeed the greatest common divisor.

Example 2: Tabular form with large numbers

Question: Find the GCD of $1071$ and $462$ using a table.

Method:

1. Create columns for the Dividend, Divisor, Quotient, and Remainder.
2. Divide $1071$ by $462$ to find the first row's values.
3. Shift the Divisor and Remainder left into the next row.
4. Continue dividing until you reach a Remainder of $0$.

Answer: The greatest common divisor is $21$.

Check: $1071 \div 21 = 51$ and $462 \div 21 = 22$. Because $51$ and $22$ have no common factors, the GCD is correct.

Example 3: Checking for coprime numbers

Question: Use the Euclidean algorithm to find the GCD of $100$ and $23$.

Method:

1. $100 = 23 \times 4 + 8$
2. $23 = 8 \times 2 + 7$
3. $8 = 7 \times 1 + 1$
4. $7 = 1 \times 7 + 0$
5. The last non-zero remainder is $1$.

Answer: The GCD is $1$. This confirms that $100$ and $23$ are coprime numbers.

Check: Since $23$ is a prime number and does not divide evenly into $100$, their only shared factor is $1$.

How to Check the Answer

To verify your result from the Euclidean algorithm, you must perform two simple division checks.

First, divide both of the original numbers by your final GCD.

They must both divide evenly with a remainder of zero. Second, examine the two quotients you just produced. If they share any common factor greater than $1$, your algorithm calculation is incorrect, and your GCD is too small.

Common Mistakes

Choosing the quotient instead of the remainder

The most frequent mistake happens at the final step when the remainder hits zero. Students often look at the multiplier (the quotient) instead of the number being divided by (the divisor or previous remainder). The GCD is always the divisor that produced the zero remainder.

Not completing the final division

Some students stop the algorithm as soon as they see a small number, assuming they have reached the end. You must continue shifting and dividing until the remainder is exactly zero. The last non-zero remainder is your answer, even if it takes several more steps to prove it.