Greatest Common Divisor or Highest Common Factor

Greatest Common divisor or highest common factor(the name says it all) of two or more numbers is the highest of the common factors of all the numbers. To find GCD of 12 and 8, first write down all the factors of the two numbers

12 -> 1,2,3,4,6,12

8 -> 1,2,4,8

The common factors of 8 and 12 are 1,2 and 4. HCF or GCD is the highest among these common factors. So HCF or GCD is 4.

Lets find GCD of 12,24 and 28

12 -> 1,2,3,4,6,12

24-> 1,2,3,4,6,12,24

30->1,2,3,5,6,15,30

Common factors in all three numbers are 1,2,3 and 6. Hence the GCD is 6.

For 9 and 26,

9 -> 1,3,9

26->1,2,13,26

There is no common factor other than 1. So the HCF is 1. When you don’t have any common factors other than 1, the numbers are known as “coprimes”.

Why should you find GCD? What are some applications of it?

  1. One very common application of GCD is simplifying fractions. If you want to simplify 216/360, you might try dividing numerator and denominators separately by all of its common factors that you can think of – say 9, 4 and then 2. You will end up with 3/5. But if you divide the fraction directly with its GCD  which is 72, then you can do the simplification in a single step. If you think simplifying with common factors is easier than finding GCD, you should think of the bigger picture. What about very big numbers? If we write a computer program, it can quickly find GCD and simplify the fraction in one step.
  2. GCD has infinite number of applications in measurements. If you want to floor a rectangular room with minimum number of square tiles, you can use GCD straightaway. Another example is – If you have 2 containers that can hold so and so litres of liquid (and assume that you have some extra containers to offload), what are all the possible measurements you can find out with those containers?
  3. GCD and its extended concepts have a numerous applications including finding RSA private keys, continued fractions, chinese remainder theorem etc,.

GCD or HCF by prime factorization:

Lets find the GCD of 12,24 and 30 by some other approach. Write down each number as a product of smallest possible numbers.

12 = 2*2*3

24 = 2*2*2*3

30 = 2*3*5

How is this going to help find GCD? Take 12 = 2*2*3, we can find all the factors of 12 from 2,2 and 3. How? These numbers itself are definitely factors. In order to get other factors of 12, you just have to multiply these numbers with each other in all possible combinations.

2*2 = 4, 2*3 = 6, 2*2*3=12. We already have 2 and 3. Include 1 and now you have all factors of 12.

Similarly, take 24 and try finding the product of the numbers in all possible combinations.

2*2 =4, 2*3=6, 2*2*2 =8, 2*2*3=12, 2*2*2*3=24. If you include 1 and the smaller numbers themselves, you got all factors of 24.

Since we have written down the numbers as a product of smallest possible numbers, you cannot split these numbers further. It means those numbers don’t have any factors (ofcourse otherthan 1 and the number itself). Thats the definition of prime numbers. We have written the numbers as product of its prime factors. When you have prime factors, you can play around and get all the factors of the number.

So, how to find GCD? Since, we know that we get all the factors of a number from its prime factors, first pick the common prime factors of the numbers that you want to find the GCD for. You have the common prime factors now. You need the ‘greatest common factor’. You don’t have to find all the factors- just the biggest one. To get the biggest one, just multiply all the common prime factors. Then, you are done! you have the GCD.

Since, I have described the approach in detail, it sounds like a big task. Its much easier than writing all the factors.

12=2*2*3

24=2*2*2*3

The common numbers are 2,2 and 3(Don’t leave out the repeated numbers. It is needed to find the biggest factor). 2*2*3 = 12. GCD of 12 and 24 is 12.

30=2*3*5. Common prime factors for all 3 numbers are 2 and 3. 2*3 = 6 is the GCD of 12,24 and 30.

If you cannot find any common factors, GCD is 1. Because, ideally we should write 12 as 1*2*2*3. 1 is a common factors for all the numbers.

Quickly another example – 42,56

42 = 2*3*7 

56 = 2*2*2*7

Common prime factors are 2 and 7. 2*7=14 is the GCD of 42 and 56.

GCD by repeated division or ladder method:

We are only concerned about the common factors of the numbers. We don’t even care about the numbers that are left out. So, why should we waste time in finding those unnecessary factors? Try and divide both the numbers you want to find gcd for with possible common factors as shown in the picture.

 

Just multiply all the common factors to get the GCD. This method can be called as repeated division or successive division or continuous division or inverted birthday cake or ladder method.

Euclidean Algorithm:

Calculate GCD of 5234 and 4826. Writing down prime factors is not that difficult, but sounds cumbersome. Well, Euclid, an extraordinary Greek mathematician known as ‘father of geometry’ have given us a wonderful algorithm to find GCD easily.

GCD(a,b) = GCD(b,a%b).  [ Assuming a>b. If not, just swap]

He has given us a way to make the numbers smaller and smaller until we are able to handle it easily.  Ideally, you have to keep doing it until you have 0 as one of the number. GCD(x,0) is x. I have explained the proof of eucledian algorithm (a proof based on examples not just a theoretical one) in another post. Check it if you are curious on how it works.

Lets apply this for our example.

GCD(5234,4826) = GCD(4826,408)

                             = GCD(408,338)

                              =GCD(338,70)

                               =GCD(70,58)

                               = GCD(58,12)

                               =GCD(12,10)

                               =GCD(10,2) 

          =GCD(2,0) = 2

GCD of the numbers is 2. It might be difficult for you to calculate the modulo and the difference. But imagine doing it with a computer program. Is it not efficient  when compared to our previous approaches?

If you try to write 5234 and 4826 as a product of its prime factors,

5234 = 2 * 2617

4826 = 2 * 19 * 127

2617 and 127 are both prime numbers and cannot be factorized further. To confirm that 2617 is a prime number itself will take atleast  51 divisions (sqrt(2617)  = 51.2). But Euclids algorithm made use of only 8 divisions in total.

Lets quickly see another example. GCD(330,460)

GCD(330,460) = GCD(460,330) = GCD(330,130)

                                                    = GCD(130,70)

                                                    =GCD(70,60)

                                                    =GCD(60,10)

                                                     =GCD(10,0) = 10

If you want to find gcd of 3 numbers using this algorithm, first find gcd of any 2 numbers and then find gcd of the result with the third number.