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 n

Example: 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 = 221

Key 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

googletag.cmd.push(function() { googletag.display('div-gpt-ad-1492166336268-0'); });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^(n-1) * b + C(n,2) * a^(n-2) * 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 = 890

Divisibility 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^nDivisibility 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 n-digit 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 11Divisibility 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 n-digit 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.