• Skip to main content
  • Skip to secondary menu
  • Skip to primary sidebar
  • Skip to footer
  • CAT Online Coaching
  • CAT Coaching in Chennai
  • Bharath’s Reading List
  • CAT Preparation
    • How to Prepare for CAT Exam
      • How to Prepare for CAT Quantitative Aptitude
      • How to prepare for CAT DILR
      • How to prepare for CAT VARC
    • 2IIM’s CAT Questions
    • CAT Syllabus
    • CAT Previous Year Paper
    • What is CAT Exam all about?
  • 2IIM CAT Preparation Reviews

2IIM CAT Preparation Blog

The Best CAT Online Coaching

Best Online CAT Coaching

  • Email
  • Facebook
  • Instagram
  • LinkedIn
  • Phone
  • YouTube
You are here: Home / CAT Quantitative Aptitude / A Beautiful way of finding GCD of two numbers | Number Theory | CAT 2021

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

September 11, 2021 By Rajesh 4 min read

visit 2iim
Enroll now

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 23 *32 * 5 and 168 as 23 * 3 * 7 and then see that both have a 23 * 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?

Mind blowing

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.

visit 2iim
Enroll now

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.

Share this:

  • Twitter
  • Facebook
  • WhatsApp

Reader Interactions

Leave a Reply Cancel reply

Primary Sidebar

Recent Posts

  • Can a Weak Student Crack CAT Exam?
  • Reading List | This Week | March 3rd week 2023
  • What should you look for in Online CAT Coaching?
  • Online CAT Coaching Vs Classroom CAT Coaching: Which is Best?
  • Reading List | This Week | March 2nd week 2023

Categories

  • Announcements (40)
  • B-School Selection Process (10)
  • CAT 2020 (33)
  • CAT 2021 (82)
  • CAT 2022 (21)
  • CAT Coaching (2)
  • CAT DILR (20)
    • Data Interpretation For CAT (5)
    • Logical Reasoning For CAT (7)
  • CAT Gyan (103)
  • CAT Live Sessions (2)
    • CAT Meetup (1)
  • CAT Preparation Strategy (193)
    • Achievers talk (6)
    • Announcements (29)
  • CAT Quantitative Aptitude (30)
  • CAT Reading List (175)
    • Economy Business (1)
    • Fiction Others (1)
    • Humans Culture (2)
    • Politics Law Crime (2)
    • Psychology & Philosophy (2)
    • Reading List – This Week (164)
    • Technology Industry Science (2)
  • CAT Verbal Ability (20)
    • CAT Reading Comprehension (11)
  • CAT WAT GDPI (18)
  • GMAT (2)
  • IIFT 2022-2024 (1)
  • IPMAT (3)
  • MAH-CET Preparation (1)
  • mba (37)
    • rural management (1)
  • MICAT (1)
  • Mock CATs (5)
  • NMAT (3)
  • PGDBA Examination (2)
  • SNAP 2021 (1)
  • Top B-schools (5)
  • Uncategorized (14)
  • XAT 2021 (4)
  • XAT 2022 (2)
  • XAT Preparation (10)
    • Announcements (3)

Archives

  • March 2023 (6)
  • February 2023 (8)
  • January 2023 (5)
  • December 2022 (2)
  • November 2022 (5)
  • October 2022 (3)
  • September 2022 (10)
  • August 2022 (9)
  • July 2022 (18)
  • June 2022 (22)
  • May 2022 (17)
  • April 2022 (9)
  • March 2022 (4)
  • February 2022 (6)
  • January 2022 (4)
  • December 2021 (1)
  • November 2021 (4)
  • October 2021 (12)
  • September 2021 (14)
  • August 2021 (32)
  • July 2021 (31)
  • June 2021 (22)
  • May 2021 (9)
  • April 2021 (5)
  • March 2021 (14)
  • February 2021 (15)
  • January 2021 (21)
  • December 2020 (19)
  • November 2020 (8)
  • October 2020 (14)
  • September 2020 (33)
  • August 2020 (31)
  • July 2020 (31)
  • June 2020 (12)
  • May 2020 (9)
  • April 2020 (8)
  • March 2020 (12)
  • February 2020 (10)
  • January 2020 (14)
  • December 2019 (5)
  • November 2019 (5)
  • October 2019 (7)
  • September 2019 (11)
  • August 2019 (6)
  • June 2017 (1)
  • October 2015 (1)
  • August 2015 (1)
  • January 2011 (1)

Follow Us!

  • Email
  • Facebook
  • Instagram
  • LinkedIn
  • Phone
  • YouTube

Footer

The heights by great men reached and kept were not attained by sudden flight,
but they, while their companions slept,
were toiling upward in the night.

- Henry Wadsworth Longfellow

Copyright © 2019. All rights reserved by 2iim.com - A Fermat Education initiative. Privacy policy | Terms & Conditions