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 2^{n }if the last n digits are divisible by 2^{n}
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 33Is 22977 divisible by 333 ?
Take 3 digits from right at a time and find the sum.
977 + 022 = 999, hence divisible by 333Is 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 5^{n }if the last n digits are divisible by 5^{n}
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 7Divisible 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 11What is the remainder when 10^{5 } 560 is divided by 11 ?
10^{5 } 560 = 99440
(0 + 4 + 9 )  ( 4 + 9 ) = 0 => divisible by 11. so Remainder[(10^{5 } 560) / 11] = 0Divisible by 101: Mark off the number in groups of two digits starting from the right, and add the twodigit 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 threedigit 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 10^{n }+ 1 : Mark off the number in groups of n digits starting from the right, and add the ndigit groups together with alternating signs. If the sum is divisible by 10^{n} + 1 then the original number is also divisible by 10^{n} + 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 111To 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 2^{3} and 3 as 24 = 2^{3} * 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 10
Step 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] = 0OK! 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