Divisibility Rules - Anubhav Sehgal, NMIMS Mumbai

[anubhav_sehgal]

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

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 :

1. 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.
2. Divisibility by 3
   You check divisibility and remainder by calculating sum of digits of the number and dividing that by 3 or 9.
3. 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
4. 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 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 11
5. 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 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.
6. 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.