Divisibility Rules  Anubhav Sehgal, NMIMS Mumbai

Key note 1
(a^n + b^n) mod (a + b) = 0 when n is odd
(a^n  b^n) mod (a + b) = 0 when n is even
(a^n  b^n) mod (a  b) = 0 for all natural numbers
(a^n  b^n) mod (a^k  b^k) = 0 when k is a factor of nExample: 18^2000 + 12^2000  5^2000  1 is divisible by ?
323
221
299
237(18^2000  5^2000) + (12^2000  1^2000) = B1 + B2
B1 is divisible by 13 by result 3 and B2 is divisible by 13 by result 2. Hence the expression is divisible by 13.
Also, writing it as : (18^2000  1^2000) + (12^2000  5^2000) = B1 + B2
B1 is divisible by 17 by result 3 and B2 is divisible by 17 by result 2. Hence the expression is divisible by 17.
Hence the expression is divisible by 13 * 17 = 221Key note 2
Any number of the abcabc form is divisible by 1001 and hence by extension by 7,11 and 13 as 1001 = 7 * 11 * 13
Key note 3
If 10^n mod x = 1, then to find remainder for any number upon division by x, you can take n digits at a time, find individual remainders and simply add them up.
example : Find the remainder when 123123123123123...upto 300 digits is divided by 27.
Since 999 = 27 * 37. So, 1000 mod 27 = 1 Hence we can take three digits at a time and find individual remainders. 123 mod 27 = 15 and for 300 digits we'll have 300/3 = 100 such sets.
So, finally we have 15 * 100 mod 27 = 15 = Remainder.Key note 4
(a^n + b^n + c^n + ...) mod (a + b + c + ...) = 0 if and only if a,b,c,.. are in AP and n is ODD
Example : 16^3 + 17^3 + 18^3 + 19^3 mod 70 = ?
Answer : Zero.
As 16,17,18,19 are in AP and 3 is odd.
Hence the expression is divisible by sum of the base terms : (16 + 17 + 18 + 19) = 70.Key note 5
Any digit or a set of digits repeated (p  1) times is divisible by p.
example : 121212121212 mod 7 = ?
Answer : Zero.
Since 12 12 12 12 12 12 is a repeated set of 12 coming 6 (=7  1) times. Hence is divisible by 7.Using Binomial Theorem
(a + b)^n = C(n,0) * a^n + C(n,1) * a^(n1) * b + C(n,2) * a^(n2) * b^2 + .... C(n,n) * b^n
Example : Find the remainder when 7^25 is divided by 36.
7^25 = (6 + 1)^25 = C(25,0) * 6^25 + C(25,1) * 6^24 + ... + C(25,23) * 6^2 + C(25,24) * 6 + C(25,25)
All terms except last two terms will be divisible by 36.
So, 7^25 mod 36 = [C(25,24) * 6 + C(25,25)] mod 36 = (25 * 6 + 1) mod 36 = 151 mod 36 = 7.Using factor theorem and remainder theorem
If g(x) divides f(x), we say that f(x) is divisible by g(x) or g(x) is a factor of f(x).
Also, when a polynomial f(x) is divided by (x  a) then remainder is given by f(a)example 1 : What is the remainder when x^4  3x^2 + 1 is divided by (x  2)
Let f(x) = x^4  3x^2 + 1. Then, remainder = 2^4  3*2^2 + 1 = 5
example 2 : What is the largest value of n for which n^3 + 100 is divisible by (n + 10).
We substitute n = 10 in the polynomial to get (10)^3 + 100 = 900
(n + 10) must be now a factor of 900
k(n + 10) = 900
For largest value of n, k = 1
n = 890Divisibility Rules :
 Divisibility by 2 , 4 (=2^2) , 8 (=2^3) , 16(2^4) , ...
You check divisibility and remainder by last n digits of the number when number divided by 2^n.  Divisibility by 3
You check divisibility and remainder by calculating sum of digits of the number and dividing that by 3 or 9.  Divisibility by 5, 25(=5^2) , 125(=5^3) , ...
You check divisibility and remainder by last n digits of the number when divided by 5^n  Divisibility by numbers of the form 10^n + 1 : 11, 101, 1001 , ...
Break the number in groups of n digits starting from the right and add the ndigit groups with alternate + and  signs. If the sum is divisible by 10^n + 1, then the number is divisible by 10^n + 1
Why this happens?
Any number abcd(say) can be written as : a * 10^3 + b * 10^2 + c * 10 + d
Now let us take remainder by 11.
Since 10 mod 11 = 10 or 1.
We have 10^n mod 11 = 1 when n is odd and 10^n mod 11 = 1 when n is even
Hence we get, abcd mod 11 = (a + b  c + d) mod 11  Divisibility by numbers of the form 10^n  1 : 9, 99, 999, ..
Break the number in groups of n digits starting from the right and add the ndigit groups. If the sum is divisible by 10^n  1, then the number is divisible by 10^n  1
Why this happens?
Since 10 mod 9 = 100 mod 99 = 1000 mod 999 = 1 and so on
So writing a number say abcd as ab * 10^2 + cd, we can find remainder by 99 as : (ab*10^2 + cd) mod 99 = (ab + cd) mod 99 which is nothing but groups of 2 from the right.  Divisibility by any prime greater than 5: Seed number method
How to find seed number ?
We need to find a multiple of prime number that ends up in 10k +/ 1 form. Usually this would happen within the first 10 multiples of the prime. example: Let 13 be the prime.
13 * 3 = 39 = 4 * 10  1 form => Seed number = 4
13 * 7 = 91 = 9 * 10 + 1 form => Seed number = (9)
NOTE: Seed number method is applicable to other base systems too with the only change that you look for bk +/ 1 format for a given base b
How to use seed number for divisibility?
Break the number into unit digit, denoted by B and remaining digits, denoted by A. Now if the seed number is N, then check for divisibility for A + NB and if the seed number is (N) then check for divisibility for A  NB.
 Divisibility by 2 , 4 (=2^2) , 8 (=2^3) , 16(2^4) , ...