In mathematics, the **greatest common divisor** (**gcd**) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4.

Click here for more *Questions on Aptitude*

Trick 109 – Find HCF Mentally without Factorization

A common multiple is one that is a multiple of 2 or more than 2 numbers. **For example:**

**The common multiples of 2 and 3 are 6,12,18, etc**

- The Least Common Multiple of 2 numbers is the smallest positive number that is a multiple of both.
- In other words, the Least Common Multiple of 2 or more numbers is the smallest number which is divisible by all the given numbers.

- Multiples of 2: 2,4,6,8…
- Multiples of 3: 3,6,9,12…
- LCM of 2 and 3 will be 6.

**How To Find Out LCM:**

**Method 1: Prime Factorization Method**

- Factorize all numbers into their prime factors
- Make a note of all the distinct factors
- Raise each factor to the maximum power present and multiply them all
**Example:****To find the LCM of 136,144,168**

136 = 2^{3} x17 144 = 2^{4} x 3^{2} 168= 2^{3}x3x7 Distinct factors are 2, 17, 3 and 7. The highest power of 2 is 4, of 3 is 2, of 17 is 1 and of 7 is 1. So, LCM = 2^{4} x 3^{2} x17 x7 = 17136 **2. Method 2:**

- To calculate the LCM of 4, 5 and 6, take the highest number: 6 in this case.
- Now start with the multiples of 6 and check whether they are the multiples of 4 and 5 or not.
- The first common multiple (i.e. the multiple of all 3?4,5, and 6) will be the LCM.
- You start with 6, 12, 18, 24, 30, 36, 42, 48, 54, 60 So, 60 is the LCM as it is the first number to be divisible by 4,5 and 6.

**Illustrations:** **Example:** **There are some boxes lying in a straight line. Every 6 ^{th} box contains a muffin, every 8th contains a chocolate and every 9^{th} contains a soft-toy. Which is the first box to have all 3 items?** a) 48 b) 36 c) 432 d) none of these

**Highest Common Factor (HCF)**

Greatest Common divisor (GCD), also called HCF, is the largest integer that perfectly divides two or more given numbers. **For Example:** **The HCF of 18 and 12 is 6.** 6 is the largest number that divides both 18 and 12. **How To Find Out HCF:** **Method 1: Prime Factorization Method-**

- Factorize all numbers into their prime factors
- Make a note of all the distinct factors present in all three numbers
- Raise each factor to the minimum power present and multiply them all

**Example: To find the HCF of 136,144, 168** **To find the HCF of 136,144, 168** Step 1: 136 = 2^{3} x17 144 = 2^{4} x 3^{2} 168= 2^{3}x3x7 Step 2: Distinct factors present = 2,3,7,17 Step 3: Raising each factor to the minimum present (i.e. 2^{3},3^{0},7^{0} and 17^{0}) HCF= 2^{3}=8 **Method 2: Division Method**

- To find the HCF of 2 numbers by Division Method, the higher number is divided by the lower number.
- Then the lower number is divided by the remainder obtained in the previous division.
- This remainder is divided by the next remainder and so on till the remainder is zero. The last divisor will be the HCF of the two numbers

**Example:** **To find the HCF of 12 and 15** **To find the HCF of 12 and 15** 15/12|R = 3 12/3|R=0 Thus, the HCF= 3 **HCF and LCM of Fractions** HCF of fractions = HCF of numerators/ LCM of denominators LCM of fractions = LCM of numerators/ HCF of denominators LCM x HCF = Product of two numbers (this can be applied only for 2 numbers) **Question: The circumference of the wheels of a vintage car are 7/3 and 13/4 m respectively.****A mark is made on each of these wheels at their point of contact with the ground.Find the distance traveled by the car before which the part of the wheels with the marks is again on the ground at the same time next time.** a) 85 m b) 183 m c) 91m d) None of these **Solution:** Option (c) LCM of 7/3 and 13/4 gives the answer = LCM of numerators/ HCF of denominators = 91/1= 91.

- The HCF of two or more numbers is lesser than or equal to the smallest of those numbers
- The LCM of two or more numbers is greater than or equal to the greatest of those numbers
- If a number X always leaves a remainder R when divided by the numbers A,B,C.., then X= LCM(or a multiple of LCM) of A,B,C…+R

**Illustrations:**

**Find the highest number less than 2000 which is divisible by all of 4,6,8,10 and 12**

**Solution:** Find the LCM of 4,6,8,10 and 12 = 120 A multiple of 120 less than 2000= 1920 thus, this is the number which is divisible by 4,6,8,10 and 12 Find the LCM of 4,6,8,10 and 12 = 120 A multiple of 120 less than 2000= 1920 thus, this is the number which is divisible by 4,6,8,10 and 12.

**Find the largest 4 digit number divisible by 45, 50 and 30**

**Solution:** 45=5×32 50=52×2 30=2x3x5 LCM of 45,50 and 30 =52x2x32 = 450 Largest 4 digit number = 9999 9999/450 leaves a remainder of 99 Thus, 9999-99=9900

**Example:****A is running at a speed of 10 m/s and B is running at a speed of 20 m/s around a circular track of length 500 m in the same direction. After how much time will they be at the starting point together for the first time if they start running at the same time.****Solution:**They will meet at the LCM of the time taken by both of them to run around the circleTime taken by A to run around the circle once= distance/speed = 500/10= 50sTime taken by B to run around the circle once= distance/speed= 500/20= 25sLCM= 50, thus they will be together after 50 seconds**A can do a piece of work in 5 days. B can do the same piece of work in 6 days. How long will they take to do the work together?****Solution:**Let us assume the total units of work = a multiple of both 5 and 6 =LCM(5,6) =30 unitsHence, A does 30/5= 6 units of work per day And B does 30/6= 5 units of work per dayTogether they will do 6+5=11 units of work per dayThus they will take 30/11 = 2 8/11days to do the work together.