How to find GCD of two numbers?

I am reading Scott Aaronson’s lecture notes on Great Ideas in Theoretical Computer Science to get inspiration and overview of the field. The notes encompass logic, math, computational complexity, cryptography, quantum computing and more.

If we are given two numbers A and B, how do we find the greatest common divisor (GCD)? This is a simple question and we have been taught how to find it in primary school, to recap, GCD is the biggest number that divides both A and B.

The simple method is to use Division by primes method. We divide A and B by the smallest common prime divisor, further divide the remainder by the smallest common prime divisor, continue until no common prime that can divide them, multiply all the prime divisors, the result is GCD.

\begin{array}{ll} 3 \underline{|63 \quad 84} \\ 7 \underline{|21 \quad 28} \\ \enspace 3 \quad \enspace 4 \end{array}

3 \times 7 = 21

The second method, prime factorization, is similar to the first. We factor A and B into their prime factors, 63 = 3 \times \bf{3 \times 7}, 84 = 2 \times 2 \times  \bf{3 \times 7}, multiply the common primes factors of A and B, \bf{3 \times 7} = 21, the result is GCD. Both methods are similar because they multiply all the common primes to get GCD.

The above two methods has a drawback, that is the factorization of number into its prime factors is hard, it requires many steps, this is especially so with big numbers. Factorizing big numbers into their prime factors is so hard that banks assume no computer can do it fast enough, this is used in encryption. (A minor distinction: The RSA encryption used by bank generates big number that is made up of only 2 prime factors, while the prime factorization we are doing here is on number that is made up of 2 or more prime factors, it seems that the ways to factorize number in both cases are different.)

Euclid, 3rd Century BC Greek mathematician introduced the Euclid difference algorithm and Euclid remainder algorithm to find GCD. Euclid difference algorithm says replace the bigger number by the difference of the bigger number and the smaller number, GCD(63, 84) = GCD(63, 84-63) = GCD(63, 21) = GCD(63-21, 21) = GCD(42, 21) = GCD(42-21, 21) = GCD(21, 21), stop when the two numbers become the same, the result is GCD.

Euclid remainder theorem says replace the bigger number with the remainder of the division of the bigger number by the smaller number, GCD(63, 84) = GCD(63, 84%63) = GCD(63, 21) = GCD(63 %21, 21) = GCD(0, 21), the % sign is modulo, the result of a modulo operation is the remainder, stop when one number becomes 0, the result is GCD.

How does The Euclid difference algorithm compared to Euclid remainder algorithm? Imagine we have a very small A and a very big B, e.g. 63 and 300000000, the difference algorithm requires us to keep taking away 63 from 300000000, this takes a long time before 63 gets the chance to be the bigger number. The remainder theorem takes significantly shorter time, because for each iteration, the bigger number becomes the remainder.

So far, the best method to find GCD is the Euclid remainder algorithm. Why do we have to bother with algorithm? Computer needs step by step instructions, and the algorithm provides that, the computer just have to assign the remainder to the variable A or B (whichever is bigger), continue until one variable becomes 0 using while loop. We can also code the prime factorization method to find GCD but as previously said, the time it takes to find the GCD using this method is longer than the Euclid’s method.

Update: I have written a simple script to compare the number of steps taken using Euclid difference algorithm and Euclid remainder algorithm.

Leave a Reply