Divisibility Problems Tips and Tricks

There are three numbers a, b and c. You have to find out the largest number x that divides all the 3 numbers.

Way to solve Type 1 Question

Now a is the greatest number, b is the 2nd largest of the three and c is lowest.

Find the HCF of (a – b), (b – c) and (a – c)

e.g. The greatest number that will divide 63, 138 and 228 so as to leave the same remainder in each case:

a = 228, b = 138 and c = 63

HCF of ((228-138),(138-63),(228-63))
HCF of (90,75,165)
75=3*5*5
90=2*3*3*5
165=3*5*11

Thus HCF is 3*5 = 15

When there is a number is N, when divided by another number a, the remainder is r₁. When the same number is divided by a number b, then remainder is r₂. What is the number ?

Clearly,

• N = x(a) +r₁, where x is natural number
• N = y(b) + r_2,where y is a natural number.

Lets see with an example –

What is the smallest four number which when divided by 6, leaves a remainder of 5 and when divided by 5 leaves a remainder of 3?

• N = 6x +5 and N = 5y + 3
• so 6x +5 = 5y + 3
• => y-x = (x+2)/5

Thus a+2 should be divisible by 5 smallest value would be x =3.

• so y – 3 = (3+2)/5 => y = 4
• Thus N = 6x +5 = 23

Now to calculate largest 4 digit number –

• Find remainder by dividing 1023/23 => remainder 11 as (smallest 4 digit number + N)/ N = Remainder 11.
• Number = 1023 – 11 = 1012.

Now in the same Question if you had to find largest 4 digit number then same thing but new equation 

The number less than 1000 exactly divisible by 6 is 996. And 995 is the number exactly divisible by 5 and less than 1000.

• Let the number be x
• x = 996+6p+5 and x = 995+5q+3
• => 996+6p+5 = 995+5q+3
• => 1001+6p = 998+5q
• => 3+6p = 5q
• the lowest integer pair satisfying this equation would be (p,q) = (2,3)
• => x = 996+6*2+5 = 995+5*3+3 = 1013.

Greatest power of p that will divide N!

This can be solved directly by a formula –

[N/p] + [N/p²] + [N/p³] …..

e.g. for 40! and 5

[40/5] + [40/5²] + [40/5³] …..

8 + 1 + 0 = 9

Thus, the Answer is 9.

Number of 0’s in x!

100! = 100 * 99 * 98 * … * 2 * 1

A trailing zero is formed when a multiple of 5 is multiplied with a multiple of 2. Now all we have to do is count the number of 5’s and 2’s in the multiplication.

Let’s count the 5’s first. 5, 10, 15, 20, 25 and so on making a total of 20. However there is more to this. Since 25, 50, 75 and 100 have two 5’s in each of them (25 = 5 * 5, 50 = 2 * 5 * 5, …), you have to count them twice. This makes the grand total 24. For people who like to look at it from a formula point of view

Number of 5’s = 100/5 + 100/25 + 100/125 + … = 24