Tips for finding GCD quickly

It is very important to clearly understand various methods of finding GCD before reading this post. In my previous post regarding GCD, we have discussed the following methods,

Factorization

Prime Factorization

Ladder

Euclid’s Algorithm

 

Tip 1:

Lets first see a shortcut for finding GCD using factorization with mind math. You need to set a threshold under which you are comfortable working on numbers in your mind. Lets have threshold as 50 for this post.

Example 1 – 18,30,36

Choose the smallest number for calculation. Why? GCD has to be the divisor of all the given numbers. Numbers between 19 and 30 or 19 and 36 definitely cannot be GCD (because they cannot be divisors of 18. 18 is the greatest factor for 18). We don’t have to waste our time by dealing with numbers between our smallest number and biggest number. So lets pick 18 here.

Calculate factors of the smallest number in descending order one by one. Check if the factor divides all other given numbers. If it divides, you have found the GCD. Why and How? Well, we are dealing with greatest common factor. If you start from 1, you will find some common factors but you will not be sure if it its the greatest one, as there will be numbers bigger than this that might be common divisor for all numbers. So we are starting with the chosen number (smallest of the given numbers) and working our way down to find the GCD quickly.

How to quickly check the factors?

In our chosen example, 18 is the smallest number. First check if 18 (18/1) itself divides other two numbers. It will not divide 30 evenly. So check next factor.

To find the next biggest factor of 18 – divide 18 by 2.  We get 9. Does 9 divide both 30 and 36 evenly? No, it doesn’t divide 30. So 9 cannot be the GCD.

Next, 18/3 = 6. Does 6 divide 30 and 36 evenly? Yes. So 6 is the GCD.

To sum up ,

  1. Pick the smallest number and check if it divides all other given numbers. If yes, then the smallest number is the GCD.
  2. If not, divide the smallest number by 2. If the answer is a perfectly divides the other given numbers, then it is the GCD.
  3. If not, continue dividing by 3,4,5…. Check if each answer divides other numbers evenly. If yes, you have found GCD. If not, continue this until you find that Common factor.

Lets see more examples

Example 2 : 14,28

Smaller number is 14

Does 14 divide 28? Yes. GCD is 14

Example 3: 18, 27,45

Does 18 divide both 27 and 45? No

Does 9 (18/2) divide both 27 and 45? Yes. GCD is 9.

Example 4: 15,30,45

Does 15 divide both 30 and 45? Yes. GCD is 15

Example 5: 24,36,44

Does 24 divide 36 and 44? No

Does 12 (24/2) divide both 36 and 44? No (36 – yes but not 44)

Does 8 (24/3) divide both 36 and 44? No

Does 6 (24/4) divide both 36 and 44? No

Does 4 (24/5 not possible so 24/6) divide both 36 and 44? yes. GCD is 4.

Lets extend this logic even if one of the numbers is less than 50 if it is easy enough for us to manipulate the other number. We can also use it for bigger numbers which are multiples of 10 as it is easier to handle.

Example 6: 25,75

Does 25 divide 75? Yes, GCD is 25.

Example 7: 150,200

Does 150 divide 200? No

Does 75(150/2) divide 200? No

Does 50(150/4) divide 200? Yes. GCD is 50.

Example 8: 48,60

Does 48 divide 60? No

Does 24(48/2) divide 60?No

Does 16(48/3) divide 60? No

Does 12(48/4) divide 60? Yes. GCD is 12.

In this example, Just by looking at 48,60 you can say 48 is 12*4 and 60 is 12*5. There is nothing common between 4 and 5 (co primes). So 12 has to be the GCD.

Tip 2:

In previous example, 44 is 4*11. 11 is prime and cannot be a factor at other numbers. So GCD has to be 4. It is not always necessary to pick small number first. If other big numbers have very few factors which you can observe immediately, it is better to pick that number for calculation.

Example 9: 15,33

Don’t start factorizing 15. 33 is 3*11. 11 is prime and is not a factor of 15. But 3 divides 15. So GCD is 3.

Note that you concluded this only because 11 cannot be a factor of 15.

Example 10: 24,32

32 is 4*8 and 24 is 4*6. But 4 is not the GCD. Because for 32, 4 is paired with 8 and similarly for 2, 4 is paired with 6. Here 8 and 6 are not co primes. They still have a common factor of 2. So be careful not to make such mistakes.

24 is 8 * 3

32 is 8 * 4.  3 and 4 are co primes. So GCD is 8.

Here, you can even apply Euclid’s algorithm. 32-24 is 8. So instead of finding GCD of 24 and 32, just find the GCD of 24 and 8. 24 is a multiple of 8. So GCD is 8.

Tip 3:

Use Euclid’s algorithm if it is easy to find difference/modulo for the given numbers ( or any 2 numbers) and if it will help. If you are not familiar with the algorithm check the implementation and proof.

Just by looking at the numbers you have to quickly decide if Euclid’s algorithm will help or not.

Example 11: 55,61

It is same as gcd of 55 and 6. GCD cannot be 6 or 3 or 2 (factors of 6 which 55 won’t divide). So GCD is 1.

Example 12: 88,92

It is same as GCD of 88 and 4. 88 is a multiple of 4. So GCD is 4.

Example 13: 72,10

It is same as GCD 10 and 2 (72%10). GCD is 2.

Let us see how to select the method in following examples.

Example 14: 92,20

Its easier to find modulo.

It is same as GCD 20 and 12 (92%20)

Now use tip 1. 12 (12/1) or 6(12/2)  are not factors of 20. 12/3 = 4 is a factor of 20. So GCD is 4.

Example 15: 55,89

55 is 5*11 which are both primes. Both 5 and 11 are not factors of 89. GCD has to be 1.

Example 16: 12,32,36

Just apply Euclid for the bigger numbers. 36-32 = 4 gives the smallest number. It is same as GCD of 12,32 and 4. GCD is 4.

Example 17: 72,126

Better to use ladder method itself than to factorize 72. You can try using Euclid’s but I think ladder method would be easier. GCD is 18.

Example 18: 24,48

48 is a multiple of 24. GCD is 24.

Example 19: 48,92

Both numbers don’t seem to have few factors. You can try Euclid but i would jump to ladder method. GCD is 4.

Example 20: 18,42

Factors of 18 – 18,9,6….. 18 and 9 does not divide 42 but 6 does. So GCD is 6.

It all takes practice to find GCD quickly. Next time, don’t immediately jump to ladder method when you have to find GCD. Think and find GCD in your mind. I am sure you can discover many more strategies.