Basic Divisibility Rules - Ravi Handa


  • www.handakafunda.com | IIT Kharagpur


    The standard rules which nearly all of us are very comfortable with are the ones for 2^n and 5^n. For these all that one needs to do is look at the last ‘n’ digits of the number. If the last ‘n’ digits of a number are divisible by 2^n or 5^n, then the number is divisible by 2^n or 5^n and vice versa. For details about other numbers, I suggest that you read on.

    Funda 1: For checking divisibility by ‘p’, which is of the format of 10^n – 1, sum of blocks of size ‘n’ needs to be checked (Blocks should be considered from the least significant digit ie the right side). If the sum is divisible by p, then the number is divisible by p.

    Eg 1.1 Check if a number (N = abcdefgh) is divisible by 9
    9 is 10^1 – 1
    Sum of digits is done 1 at a time = a + b + c + d + e + f + g + h = X
    If X is divisible by 9, N is divisible by 9
    Also, N is divisible by all factors of 9. Hence the same test works for 3.

    Eg 1.2 Check if a number (N = abcdefgh) is divisible by 99
    99 is 10^2 – 1
    Sum of digits is done 2 at a time = ab + cd + ef + gh = X
    If X is divisible by 99, N is divisible by 99
    Also, N is divisible by all factors of 99. Hence the same test works for 9, 11 and others.

    Eg 1.3 Check if a number (N = abcdefgh) is divisible by 999
    999 is 10^3 – 1
    Sum of digits is done 3 at a time = ab + cde + fgh = X
    If X is divisible by 999, N is divisible by 999
    Also, N is divisible by all factors of 999. Hence the same test works for 27, 37 and others.

    Funda 2: For checking divisibility by ‘p’, which is of the format of 10^n + 1, alternating sum of blocks of size ‘n’ needs to be checked (Blocks should be considered from the least significant digit ie the right side). If the alternating sum is divisible by p, then the number is divisible by p.
    (Alternating Sum: Sum of a given set of numbers with alternating + and – signs. Since we are using it to just check the divisibility, the order in which + and – signs are used is of no importance.)

    Eg 1.1 Check if a number (N = abcdefgh) is divisible by 11
    11 is 10^1 + 1
    Alternating sum of digits is done 1 at a time = a - b + c - d + e - f + g - h = X
    If X is divisible by 11, N is divisible by 11

    Eg 1.2 Check if a number (N = abcdefgh) is divisible by 101
    101 is 10^2 + 1
    Alternating sum of digits is done 2 at a time = ab - cd + ef - gh = X
    If X is divisible by 101, N is divisible by 101

    Eg 1.3 Check if a number (N = abcdefgh) is divisible by 1001
    1001 is 10^3 + 1
    Sum of digits is done 3 at a time = ab - cde + fgh = X
    If X is divisible by 1001, N is divisible by 1001
    Also, N is divisible by all factors of 1001. Hence the same test works for 7, 11, 13 and others.

    Funda 3: Osculator / seed number method

    For checking divisibility by ‘p’,
    Step 1: Figure out an equation such that
    p * n = 10m +/- 1
    If we have this equation, the osculator / seed number for ‘p’ will be -/+ m (-m in case of 10m + 1 and +m in case of 10m – 1)
    Step 2: Remove the last digit and multiply it with the seed number.
    Step 3: Add the product with the number that is left after removing the last digit.
    Step 4: Repeat Steps 2 and 3 till you get to a number which you can easily check that whether or not it is divisible by p.

    Eg: Check whether 131537 is divisible by 19 or not.
    19 * 1 = 10 * 2 – 1 (Seed number is +2)
    131537 -> 13153 + 7 * 2 = 13167 -> 1316 + 7 * 2 = 1330 -> 133 + 0 * 2 = 133
    133 is divisible by 19
    131537 is divisible by 19

    Some solved examples given below. I hope that these divisibility rules will enable you to divide and conquer few of the Number Systems problems that you encounter during your preparation. You can check out my online CAT course HERE

    What is the remainder when 123456.............4647484950 is divided by 16?

    To find out the remainder from 2n, we just need to look at the last ‘n’ digits.
    = Rem [123...484950 / 16]
    = Rem [4950/16]
    = 6

    How do I find the remainder when 12345678910...99100 is divided by 16?

    The divisibility test of 2^n is that you need to check the last 'n' digits of the number.
    => To find out the remainder from 16, you need to check the last 4 digits
    => Rem [12345....99100 / 16] = Rem [9100/16] = 12

    What is the remainder when (111...) + (222...) + (333...) + … + (777...) is divided by 37?
    In each bracket, the single digit (1, 2, 3, ..., 7) is written 110 times next to itself.

    aaa = a * 111 = a * 3 * 37
    => aaa is divisible by 37
    => aaaa..... repeated 3n number of times is divisible by 37
    => (1111.....1) 108 times is divisible by 37

    Now, 1111...111 (110 times) = 111.....1100 (108 1s and 2 0s)+ 11
    => Rem [1111...111 (110 times) /37] = 11
    => Rem [2222...222 (110 times) /37] = 22
    .
    .
    => Rem [7777...777 (110 times) /37] = 77

    So, we can say that
    Remainder when (111...) + (222...) + (333...) + … + (777...) is divided by 37
    = Rem [11 + 22 + 33 + 44 + 55 + 66 + 77 / 37]
    = Rem [308/37]
    = 12

    What is the highest possible value of ‘n’ for which (3^1024) – 1 is divisible by 2^n?

    We should try and split down the number to something a little more manageable by using the simple idea of
    a^2 - b^2 = (a + b)(a - b)

    3^1024 - 1
    = (3^512 - 1)(3^512 + 1)
    = (3^256 - 1)(3^256 + 1)(3^512 + 1)
    = (3^128 - 1)(3^128 + 1)(3^256 + 1)(3^512 + 1)
    .
    .
    .
    = (3 - 1)(3 + 1)(3^2 + 1)(3^4 + 1)(3^8 + 1)...(3^512 + 1)

    This was fairly simple, right?
    Now is where the slightly more creative part begins.
    There are 11 terms given above and all of them are even
    10 of these terms have an even power of 3
    Rem [(3^2n + 1) / 4] = Rem [((-1)^2n + 1)/4] = Rem [(1 + 1)/4] = 2
    => Terms with even powers of 3 are not divisible by 4

    So in the 11 terms, 10 are not divisible by 4.
    => Each of those 10 terms will give me 1 power of 2
    => The 11th term, which is 3 + 1 = 4 will give me 2 powers of 2
    => Total powers of 2 = n = 10*1 + 2 = 12

    What is the remainder when 123456789101112131415161718192021222324252627282930313233343536373839404142434481 is divided by 45?

    We need to find out Rem [1234.....434481/45]

    This looks a little difficult if you do not any theorems for finding out remainders. Let us take a simpler approach and break down the problem into smaller parts.

    These type of questions become really simple if you understand the concept of negative remainders. Always try and reduce the dividend to 1 or -1.

    45 = 9*5

    Let us find out the remainders seaparately and combine them later

    Rem [1234.....434481/9]
    The divisibility test of 9 is to divide the sum of the digits by 9.
    The sum in this case is 1 + 2 + 3 ... 43 + 44 + 81 = 44*45 + 81
    We can see that this is divisible by 9
    => The number is divisible by 9
    => Rem [1234.....434481/9] = 0

    Rem [1234.....434481/5] = 1 (It only depends on the last digit)

    So, our answer is a number which leaves a remainder of 1 when divided by 5 and is divisble by 9.

    Consider multiple of 9,
    9, does not leave a remainder of 1 from 5. Invalid.
    18, does not leave a remainder of 1 from 5. Invalid.
    27, does not leave a remainder of 1 from 5. Invalid.
    36, leaves a remainder of 1 from 5. Valid. (This is our answer)

    What is the remainder when 1! + 2! + 3! + ... + 100! is divided by 18?

    Rem [(1! + 2! + 3! ... 100!)/18]
    6! is divisible by 18
    7! is divisible by 18
    .
    .
    100! is divisble by 18
    => We have to find out Rem[(1! + 2! + 3! + 4! + 5!)/18]
    = Rem [ (1 + 2 + 6 + 24 + 120)/18]
    = Rem [153/18] = 9

    What is the remainder when the infinite sum (1!)^2 + (2!)^2 + (3!)^2 + ⋯ is divided by 1152?

    We have to find out the remainder when (1!)² + (2!)² + (3!)² + ··· is divided by 1152
    1152 = 2^7 * 3^2
    => (6!)^2 is divisble by 1152
    => All (n!)^2 are divisible by 1152 as long as n > 5
    So, our problem is now reduced to
    Rem [((1!)² + (2!)² + (3!)² + (4!)² + (5!)²)/1152]
    = Rem[(1 + 4 + 36 +576 + 14400) / 1152]
    = Rem [15017/1152]
    = 41

    What is the remainder when 3^21 + 9^21 + 27^21 + 81^21 is divided by (3^20+1)?

    3^21 + 9^21 + 27^21 + 81^21
    = 3^21 + (3^21)^2 + (3^21)^3 + (3^21)^4
    = x + x^2 + x^3 + x^4
    where x = 3^21

    Now, 3^21 = 3(3^20) = 3(3^20 + 1) - 3
    => Rem [3^21 / (3^20+1)] = -3
    => Rem [x / (3^20 + 1)] = -3

    We can use this to find out out answer
    Rem [(x + x^2 + x^3 + x^4) / (3^20 + 1) ] = (-3) + (-3)^2 + (-3)^3 + (-3)^4
    = -3 + 9 - 27 + 81 = 60

    Is 2222^7777 + 7777^2222 divisible by 101 and 99?

    Dividing by 101
    2222 is divisible by 101 (22*101 = 2222)
    => Any power of 2222 is divisible by 101

    7777 is divisible by 101 (77*101 = 7777)
    => Any power of 7777 is divisible by 101

    If two number are individually divisible by 101, their sum is also divisible by 101.
    => 2222^7777 + 7777^2222 is divisible by 101

    Dividing by 99

    If a number is divisible by 11 and 9, it will be divisible by their LCM or 99.

    2222^7777 + 7777^2222 is divisible by 11 because the number in the base are individually divisible by 11.

    Now, let's check divisibility from 9
    Rem [2222^7777 / 9] = Rem [(-1)^7777 / 9] = Rem [ -1 / 9] = 8
    Rem [7777^2222 / 9] = Rem [1^7777 / 9] = Rem [1 / 9] = 1

    Rem [2222^7777 + 7777^2222/9] = Rem [1 + 8 / 9] = Rem [9/9] = 0
    => 2222^7777 + 7777^2222 is divisble by 9

    So, the number given to us is divisible by both 11 and 9
    => 2222^7777 + 7777^2222 is divisible by 99

    What is the remainder when 1212121... (up to 300 digits) is divided by 99?

    To find out the divisibility for 99, we need to add the digits in blocks of two from right to left.
    As a matter of fact for 999...n times, we need to add the digits in blocks of 'n' from right to left.

    So, for 12121212.... 300 digits,
    Sum of digits in blocks of two = 12 + 12 + 12.... 150 times = 1800

    Rem [121212... 300 digits/ 99]
    = Rem [1800 / 99]
    = 18

    What is the remainder when 2222.....300 times is divided by 999?

    To check divisibility by 999, check the sum of the digits taken 3 at a time

    Sum of the digits of 222.... 300 times (taken 3 at a time)
    = 222 + 222 + 222.... 100 times
    = 22200

    Rem [22000/999] = 222

    What is the remainder when 123123... (up to 300 digits) is divided by 999?

    To find out the divisibility for 999, we need to add the digits in blocks of three from right to left.
    As a matter of fact for 999...n times, we need to add the digits in blocks of 'n' from right to left.

    So, for 123123123.... 300 digits,
    Sum of digits in blocks of three = 123 + 123 + 123.... 100 times = 12300

    Rem [123123123... 300 digits / 999]
    = Rem [12300 / 999]
    = 312


Log in to reply
 

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