Divisibility Rules - Anubhav Sehgal, NMIMS Mumbai


  • NMIMS, Mumbai (Marketing)


    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.

Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.