A Beautiful way of finding GCD of two numbers | Number Theory | CAT 20214 min read

We all know about Highest Common Factor or Greatest Common Divisors of two numbers. There are several simple methods – most of which hinge of factorizing the number. For instance, if we need to find HCF of 360 and 168. We write 360 as 2³ *3² * 5 and 168 as 2³ * 3 * 7 and then see that both have a 2³ * 3 in them so the HCF should be 24.

360 = 24 * 15

168 is 24 * 7.

15 and 7 are coprime. The highest common Factor is 24.

Now, let’s step it up

Find the HCF of 5767 and 7081

The moment we factorize this we should be through. Trouble is both of these numbers are not multiples of 2, 3, 5, 7, 11, 13 or 17. I would love to keep trying this for longer but there is a part of my brain saying that one or both numbers might even be prime. It took me a long time to even verify 7, 13 and 17.

Also, it does look like we should be looking at finding a new method. Let us begin with that wonderful idea that works wonders in math but falls short almost everywhere else – an assumption. (just kidding :P)

Let us assume that the HCF of these two numbers is h. This tells us that we can write 5767 as h*m and 7081 as h*n. Now, we have not been able to identify h but we know this H divides 5767, h divides 7081. H should divide 7081-5767 = 1314. Now, we may be able to factorize 1314. 1314 = 2 * 657 = 2 * 3 * 219 = 2 * 3 * 3 * 73.

Now, if 73 divides 5767 we are through. 5767 divided by 73 gives us 79. 7081 divided by 73 is 97. Or, the HCF is 73.

Wonderful, isn’t it?

Now, let us take it a notch above

Find the HCF of 12193 and 22331.

We can straightaway see that these two look fiercely close to being prime. We try dividing by 2, 3, 5, 7, 11, 13, 17, and then we can give up. So, we go for our approach 2. H divides 12193 and H divides 22331. So, h should divide 22331-12193 = 10138. Now, 10138 is 2 * 5069. This 5069 also looks to be a weird number and we are back where we started.

So, we are going to revert to the first step but more methodically. If h divides a and b, h divides a – b. So, h divides 12193, 22331 and 10138. Now, forget about 22331. Focus on 12193 and 10138. The beauty now is h should also divide 12193-10138 = 2055. Now, we can factorize 2055 and take it from there but that is just meh.

Let us continue in the same vein. To recap, we said

H divides 12193 and 22331

This simplifies to h divides 12193 and 10138

This simplifies to h divides 10138 and 2055.

What should this simplify to?

H should now divide 2055 and 10138 – 2055. Or, 2055 and 8083.

We can go one more step further.

H should divide 2055 and 8083-2055, or h should divide 2055 and 6028.

We can keep doing this, or eventually we will be left with the remainder of dividing 10138 by 2055. This happens to be 1918.

Now, this means h divides 2055 and 1918.

Or h divides 1918, 137

Or, h divides 137, remainder of dividing 1918 by 137. 1918 = 14 * 137.

Or, 137 divides both of these numbers. This means 137 divides 1918, 2055, 6028, 8083, 10138, 12193 and 22331. Or, 12193 can be written as 137 *89 and 22331 can be written as 137*163. The HCF of the two numbers is 137.

Beautiful isn’t it?

Let us see if we can codify this?

Let us say a > b

HCF(a, b) = HCF (a-b, b). If we repeatedly do this, we can say HCF (a, b) = HCF (Remainder (a/b), b)

Let us say Remainder (a/b) = c. HCF (c, b) = HCF of (c, (Remainder of (b/c)). We can now take (Remainder (b/c)  to be d and repeat the process. At some point we will hit remainder 0 – the numbers before that give us a HCF.

Go on, take an excel file, write a few steps for this using IF, MOD functions and device a method of finding GCD of obscure pairs of numbers. The GCD of two obscure looking 10-digit prime numbers can be computer in minutes using this beautiful approach.

This is probably never going to be used in any real life context but is a beautiful idea nevertheless.

Rajesh Balasubramanian takes the CAT every year and is a 4-time CAT 100 percentiler. He likes few things more than teaching Math and insists to this day that he is a better teacher than exam-taker.