What happens if the first number is smaller than the second?

The first step will yield a quotient of $0$ and a remainder equal to the first number. The algorithm then swaps their positions in the second step, so it corrects itself automatically.

How do you handle negative integers?

Take the absolute value of both integers before starting the algorithm. Divisors of a number and its negative counterpart are identical, so $GCD(a, b) = GCD(|a|, |b|)$.

What if both integers are zero?

The GCD of 0 and 0 is undefined. The algorithm requires at least one non-zero integer to function.

How to find the GCD with the Euclidean algorithm

The Euclidean algorithm computes the greatest common divisor (GCD) of two integers by repeatedly applying the division algorithm until a remainder of zero is reached. It applies to any pair of integers where at least one is non-zero, relying on the identity $GCD(a, b) = GCD(b, a \bmod b)$ .

The setup

Identify the two integers $a$ and $b$ . Ensure $a \ge b > 0$ . If they are negative, use their absolute values since $GCD(a, b) = GCD(|a|, |b|)$ . If $b=0$ , the GCD is $a$ and the process is complete.

The steps

Divide $a$ by $b$ to find the integer quotient $q$ and remainder $r$ , writing it in the form $a = bq + r$ where $0 \le r < b$ . 2. If $r = 0$ , the algorithm terminates and $b$ is the GCD. 3. If $r eq 0$ , replace $a$ with $b$ , and replace $b$ with $r$ . 4. Repeat step 1 with the new values of $a$ and $b$ .

Checking the result

Verify that your final non-zero remainder cleanly divides both of your starting integers $a$ and $b$ . To ensure it is the greatest divisor, you can also substitute backwards using the Extended Euclidean Algorithm to express the GCD as a linear combination of $a$ and $b$ .

Common errors

A frequent error is substituting the quotient instead of the remainder into the next step. Another standard mistake is concluding the algorithm one step early or outputting zero as the GCD; the GCD is always the last non-zero remainder, never zero.

Worked example

Find the GCD of 252 and 105 using the Euclidean algorithm.

Let $a = 252$ and $b = 105$ . Step 1: Divide 252 by 105. $252 = 105(2) + 42$ . The remainder is 42. Step 2: Replace $a$ with 105 and $b$ with 42. Divide 105 by 42. $105 = 42(2) + 21$ . The remainder is 21. Step 3: Replace $a$ with 42 and $b$ with 21. Divide 42 by 21. $42 = 21(2) + 0$ . The remainder is 0, so the algorithm terminates. The last non-zero remainder is 21. Therefore, $GCD(252, 105) = 21$ .

FAQ

Run your own problem

Answer form

References: Discrete Mathematics and Its Applications by Kenneth H. Rosen · OpenStax Contemporary Mathematics, Number Theory