# Euclids Algorithm easy 3 marks in CAT 2016

Euclids Algorithm easy 3 marks in CAT 2016
A simple Quant trick that will get you an additional 3 marks in CAT 2016

A lot of CAT aspirants fear Quant section, for obvious reasons. People will tell you that its really tricky, requires in depth knowledge of the topics, difficult for non engineers and all sorts of things. But the truth is CAT Quant is not at all that difficult. It is meant for testing your logic and speed rather than core mathematical skills. And when you have less than 2 minutes to solve a question, it is always handy to know certain shortcuts and tricks. Let me share with you one such simple trick that will definitely get you 3 marks in CAT 2016.

The trick that I am going to talk about is “Euclids Algorithm”. It may look scary from the name but believe me it is rather simple. It is used for finding out the Greatest Common Divisor or what we call Highest common factor or HCF. Though in CAT papers it is hardly asked directly to find the HCF but it is required while solving a lot of different types of problems like Algebra, time and work, ratio proportion etc. So let’s get started guys. Below I have solved a simple problem and the explanation is below that.

Find HCF of 1701 & 3768

1. Write the numbers in this format – a = b * q + r
Where , a= the bigger number out of two
b= the other number
q= the quotient when a is divided by b
r= remainder of the division
3768 = 1701 * 2 + 366

2. Now switch the number ‘b’ to ‘a’ and ‘r’ to ‘b’ numbers position respectively. i.e.
1701 = 366*4 + 237

3. Repeat this until you get 0 as remainder.
1701 = 366*4 + 237
366 = 237*1 + 129
237 = 129*1 + 108
129 = 108*1 + 21
108 = 21*5 + 3
21 = 3*7 + 0

4. Now that we get 0 as remainder in the last step, we conclude that the remainder in the previous stem i.e. 3 is the HCF of numbers 1701 & 3768.

It can be observed that it saves some time by eliminating the need of separate factorization of the two numbers. But the real use of this trick is when you are asked to find out the HCFs of some complicated numbers. Suppose you are asked to find the HCF of (13^501 – 1) & (13^501 + 1). Now we can solve this question in within 30 seconds using this technique.

13^501 + 1 = (13^501 – 1)*1 + 2 13^501 – 1 = 2*(13^501 – 1) + 0 (as we know 13^501 comes to be an odd no. therefore 13^501 – 1 will give you an even number which is divisible by 2)
Hence by Euclids Algorithm we can conclude that the HCF of (13^501 – 1) & (13^501 + 1) is 2.

Some practice is recommended to get good with this trick. Hope you find this trick useful.
Join Cetking Online Shortcut workshops program for more shortcuts by Cetking..