Divide & Conquer - Divisibility Rules

• We will now learn another important concept, divisibility check of numbers. These concepts will be used extensively during prime factorization, while calculating HCF/LCM and also in finding remainders. Here we will just focus on how we can easily check whether a given number is divisible by some common divisors or not.

We will start with the most important one in the list

 Any digit repeated ( P - 1 ) times is divisible by P, where P is a prime > 5

Find the remainder when 7777.... (100 digits) is divided by 13

We know Remainder[777... 96 digits ( 12 * 8 ) / 13 ] = 0

so Remainder [ 777... 100 digits / 13 ] = Remainder [ 7777 ( remaining 4 digits) / 13 ] = 3

Now we will see some other rules which most of you are already famililar with

Divisible by 2: If the last digit is divisible by 2.
12, 142, 68…

Divisible by 4: If the last 2 digits are divisible by 4.
724, Last 2 digits (24) gives a number divisible by 4.

Divisible by 8: If the last 3 digits are divisible by 8.
1040, Last 3 digits (040) gives a number divisible by 8.

Got the pattern ?

 A number is divisible by 2n if the last n digits are divisible by 2n

Divisible by 3: Sum of digits of the number is divisible by 3.
15672, sum of digits = 1+5+6+7+2 = 21 = 3 * 7, hence divisible by 3.

Divisible by 9: If the sum of the digits is divisible by 9
972036, sum of the digits = 9 + 7 + 2 + 0 + 3 + 6 = 27, divisible by 9.

Why this is true ? Let the number be ab, where a and b are the digits. We know ab = 10a + b = 9a + (a+b). So ab is divisible by 3 (or 9) if (a+b) is divisible by 3 (or 9) :)

Divisible by 33, 333, 3333… & 99, 999, 9999…

 To check a given number is divisible by 333…3 (n digits) just see whether the sum of digits taken n at a time from right to left is divisible by 333…3 (n digits). If yes then the original number is also divisible by 33…3 (n digits) Same can be applied for checking the divisibility of a given number with 99…9 (n digits). Check if the sum of digits taken n at a time from right is divisible by 999…9 (n digits). If yes then the original number is also divisible by 99…9 (n digits)

It is easy to understand through examples.

Is 627 divisible by 33 ?
Take 2 digits from right at a time, and get the sum.
27 + 06 = 33, hence divisible by 33

Is 22977 divisible by 333 ?
Take 3 digits from right at a time and find the sum.
977 + 022 = 999, hence divisible by 333

Is 6435 divisible by 99 ?
35 + 64 = 99. As per the above rule, 6435 is divisible by 99.

How much time you need to tell whether the number 1000000998 is divisible by 999 ?

Divisible by 5: If the last digit is 5 or 0.
E.g. 625, 310 etc…

Divisible by 25: If the last two digits are divisible by 25
Eg: 125, 50 etc..

Divisible by 125: If the last three digits are divisible by 125
Eg: 1250, 3500 etc..

 A number is divisible by 5n if the last n digits are divisible by 5n

Divisible by 7: Subtract twice the unit digit from the remaining number.If the result is divisible by 7, the original number is.
14238, 1423 - 2 * 8 = 1407 = 201 * 7, hence divisible by 7

Divisible by 11: If the difference between the sum of digits at the odd place and the sum of digits at the even place is zero or divisible by 11.
1639, (9+6) - (3+1) = 11, divisible by 11

What is the remainder when 105 - 560 is divided by 11 ?

105 - 560 = 99440
(0 + 4 + 9 ) - ( 4 + 9 ) = 0 => divisible by 11. so Remainder[(105 - 560) / 11] = 0

Divisible by 101: Mark off the number in groups of two digits starting from the right, and add the two-digit groups together with alternating signs. If the sum is divisible by 101 then the original number is also divisible by 101.
Eg: 4512276, (76 + 51) - (22 + 4) = 101, hence divisible by 101.

Divisible by 1001: Mark off the number in groups of three digits starting from the right, and add the three-digit groups together with alternating signs. If the sum is divisible by 1001 then the original number is also divisible by 1001.
Eg: 9533524, (524 + 9 ) - 533 = 0, hence divisible by 1001.

 Divisible by 10n + 1 : Mark off the number in groups of n digits starting from the right, and add the n-digit groups together with alternating signs. If the sum is divisible by 10n + 1 then the original number is also divisible by 10n + 1.

Divisible by 13: If the difference of the number of its thousands and the remainder of its division by 1000 is divisible by 13.
2184, 2 - 184 = -182, so divisible by 13.

Divisible by 111: Add the digits in block of 3 from right to left. The number is divisible by 101 if the sum is a multiple of 111 or is zero.
12659328 = 328 + 659 + 12 = 999 = 111 * 9, divisible by 111

 To check divisibility by a number, check divisibility by highest power of each of its prime factors.

Eg: To check for the divisibility by 24, check for divisibility by 23 and 3 as 24 = 23 * 3
72 is divisible by 24 as 72 is divisible by 8 and 3.

Another important one for you is a generic method

 To test for divisibility by a number ( say D ), where D ends in 1, 3, 7, or 9 :Step 1: Find any multiple of D ending in 9. (If D ends in 1, 3, 7, or 9, then multiply by 9, 3, 7, or 1 respectively)Step 2: Find m by adding 1 and divide by 10Step 3: Then a number N = 10t + q is divisible by D if and only if mq + t is divisible by D.

Eg: Find the remainder when 1054 is divided by 17
Step 1 : 17 * 7 = 119
Step 2 : m = (119 + 1) / 10 = 12
1054 = 10 * 105 + 4, t = 105 and q =4
mq + t = 48 + 105 = 153 = 17 * 9, Remainder[1054/17] = 0

OK! So we got some neat tricks. But how are we going to engage them to find the remainders. Again, we will learn from some examples.

What is the remainder when 2111756 is divided by 8 ?

We know the divisibility check for 8. Just find the remainder of the number formed from the last three digits with 8. That is our answer.

Remainder [ 2111756 / 8 ] = Remainder [ 756 / 8 ] = 4

What is the remainder when 2345987572219134 is divided by 9 ?

We know the sum of the digits should be a multiple of 9. Here just find the remainder of the sum of the digits with 9.

Remainder [ 2345987572219136 / 9 ] = Remainder [ sum of the digits / 9 ] = 2

1

14

1

12

1

1

27

1