Basic concepts of Remainders - Kamal Lohia


  • Faculty and Content Developer at Tathagat | Delhi College of Engineering


    What is the remainder when 2007 is divided by divided by 7?

    It is simple; just divide 2007 by 7 to get the remainder as 5.

    Did anybody use any shortcut in this?

    I'll tell you later :)

    Another simple one:

    What is the remainder when 2008 is divided by 7?

    Now it is smarter to use the earlier known data from previous question.

    If 2007 = 7a + 5

    Then certainly 2008 = 2007 + 1 = 7a + 5 + 1 = 7a + 6.

    Ok. Next one.

    What is the remainder when 2007 × 2008 is divided by 7?

    It is simply (5 × 6) = 2 mod 7.

    Most of you use it some knowingly and some unknowingly too.

    Funda is simple: Remainders of product of some numbers is obtained by product of individual remainders of the number with same divisor.

    As 2007 = 7a + 5 and 2008 = 7a + 6

    So 2007 × 2008 = (7a + 5)(7a + 6) = (7a)2 + (5 + 6)7a + 5 × 6 = 5 × 6 mod 7 = 2 mod 7.

    Question was simple but important learning is as said above that "Remainder of Product of some number depends on Product of their individual Remainders with same divisor."

    One more thing to tell (for those who are unaware of the 'alien' phrase MOD):

    When I say 31 = 3 mod 7, that mean 31 is a number of the form 7a + 3 OR in other words, we can also say 31 leaves remainder 3 when divided by 7. So just to avoid this long sentence every time, we use this internationally used term 'mod'. I hope it'll trouble you no more throughout the session.

    Li'l advanced:

    What is the remainder when (2007 × 2007 × 2007.... 2007 times) (2008 × 2008 × 2008....2008 times) is divided by 7?

    It is equivalent to (20072007) (20082008) mod 7 = (52007) (62008) mod 7.

    Now observe that 5 mod 7 = -2 mod 7 and also 6 mod 7 = -1 mod 7.

    Remember that term before 'mod' doesn't always give the remainder. It tell us only the form of the number. e.g. 5 mod 7 = 7a + 5 = 7a + 7 - 2 = 7(a + 1) - 2 = -2 mod 7.

    Hope you got it. Now observe one more thing that we can also write:

    5 mod 7 = -2 mod 7 = -9 mod 7 = -16 mod 7 and also

    5 mod 7 = 12 mod 7 = 19 mod 7 = 26 mod 7.

    That means you can add/subtract the divisor any number of times from the number before 'mod' and it'll not change the form of the number.

    You'll realize it's use later in the session.

    Back to problem, we need to find {(-2) 2007} × {(-1) 2008} mod 7 = -(22007) mod 7.

    Further we see that 23 = 8 = 1 mod 7.

    So -(22007) mod 7 = -(23)669 mod 7 = -1 mod 7 = 6 mod 7.

    What is the remainder when 20072008 ^ 2009 is divided by 7?

    We have seen from previous question that 2007 = -2 mod 7

    So 2007 2008^2009 = (-2)2008^2009 mod 7 = (22008^2009) mod 7.

    Also we saw that 23 = 1 mod 7. So we need to see whether the power of 2 (i.e. 20082009 here) is divisible by 3 or not.

    That means we have a sub question in the original question that to find the remainder of 20082009 by 3.

    Now 20082009 = 12009 mod 3 = 1 mod 3 (as 2008 = 1 mod 3)

    Using this info in previous part, we get 20072008^2009 = (2{3k+1}) mod 7 = 2 × (23)k mod 7 = 2 mod 7

    Please read it slowly to grasp the logic completely.

    EULER's Theorem and Euler's Totient Function

    Now we know what remainder is and how to find it. But many of you might be thinking that in earlier questions we found 23= 1 mod 7 manually. What if the number is much larger and divisor is also larger number so that just by seeing, we cannot say anything specific.

    So for your comfort, EULER made a theorem which says

    Mphi(N) = 1 mod N

    where HCF(M, N) = 1 and phi(N) = Euler's Totient Function = number of numbers less than N and co-prime to N.

    For those who don't know how to find phi(N), again EULER comes to rescue. So cheers. :)

    If N = (ap) × (bq) × (cr)....where a, b, c are distinct primes and p, q, r are their respective powers

    Then phi(N) = N(1 - 1/a)(1 - 1/b)(1 - 1/c)....

    How many numbers less than 101 are co-prime to 100?

    It is simply phi(100) = 100(1 - 1/2)(1 - 1/5) = 40.

    How many numbers less than 2100 are multiples of 3 but not multiple of 2, 5 and 7?

    It is simply phi(700) = 700(1 - 1/2)(1 - 1/5)(1 - 1/7) = 240. Can you think why??

    How many numbers less than 1200 are not divisible by 15 but divisible by 12?

    It means number should be divisible by 3 and 4 but not by 5. So it is 1200(1/3)(1/4)(4/5) = 80.

    Try to grasp what I have done.

    This is a very simple logic that "Out of every three consecutive numbers, exactly one is divisible by 3 and two are not". Similarly "Out of every four consecutive numbers, exactly one is multiple of 4 and three are not" and so on. So just use it. But remember, there is one condition to abide by. If I am considering divisibility or non-divisibility by 2, 3, 5 (say), then my total number should be multiple of / divisible by 2, 3 and 5. Otherwise, you won't get the integral answer. And never try to be over smart by rounding offs or taking some nearest integer or something else.

    how many of first 100 numbers are multiple of 2 and 5 but not of 3

    First take a number nearest to 100 which is multiple of 2, 5 as well as 3 i.e. 90.

    So till 90, we get the required numbers as (1/2)(1/5)(2/3)(90) = 6.

    And after that we have 100 i.e. 1 more. So answer will be 7.

    Another type of questions:

    Find the sum of all the numbers less than 101 which are co-prime to 100.

    As we used the symmetry pattern of numbers in previous problem, that out of every 'n' consecutive numbers exactly 1 is divisible by n and remaining (n - 1) are not. Similarly, here, when I remove the multiple of 2 or 5 from first 100 numbers, the remaining co-prime numbers also depicting a pattern. Can you identify this?

    See and try to learn the logic:

    Among first 100 natural numbers, what is the pattern besides that each number is obtained by adding 1 to previous one?

    There is one more (which is applicable to basically in all APs) , that sum of first and last is same as sum of second and second-last and so on.

    Similarly, when we have only 'co-prime to 100' numbers left with us, which are 40 in number as calculated in F1, they also appear in such pattern that "sum of First and last is same as sum of second and second-last and so on" And each of this sum is equal to 100.

    Alternately, you can think of any two numbers less than 100 whose sum is 100.

    x + y = 100.

    So if x is multiple of 2, then y is also.

    If x is not multiple of 2, then y also can't be multiple of 2.

    Similarly, for 5 also.

    That means if x is not multiple of 2 as well as 5 i.e. 2 is co-prime to 100, then y is also co-prime to 100.

    That means for every co-prime number less than 100, there is another which adds up to the previous one and make the sum 100.

    So, answer for this question becomes 20 × 100 = 2000.

    Similar one...

    Find the sum of the numbers which are less than 2100 and are multiples of 3 but not multiple of 2, 5 and 7?

    With same logic, it is 120*2100 = 252000.

    Find the sum of the numbers which are less than 1200 and are not divisible by 15 but divisible by 12?

    It's not a magic trick anymore. Answer is 40*1200 = 48000.

    For how many values of n, phi (n) is odd? For example if n = 2, phi (2) = 1 is odd.

    There are no more of such values. :)

    Remainder Theorems

    Fermat’s Theorem: Mp – M is divisible by p where p is a prime number and HCF(M, p) = 1

    i.e. Mp = M mod p

    For example: 27 – 2 is divisible by 7 or 27 = 2 mod 7.

    Fermat’s Little Theorem: Mp - 1 = 1 mod p where p is a prime number and HCF(M, p) = 1.

    In later years, Euler generalize it for non-primes also as

    Euler’s Theorem: Mphi(N) = 1 mod N where phi(N) is Euler’s Totient function and HCF(M, N) = 1

    We discussed Euler’s Totient Function already.

    Let's use this to find remainders.

    Find the remainder when 5354 is divided by 19.

    That’s easy one.

    As HCF(53, 19) = 1, we can use Euler’s theorem or Fermat’s theorem as 19 is a prime number.

    So we know that 5318 = 1 mod 19

    i.e. (5318) (5318) (5318) = 5354 = (1)(1)(1) mod 19 = 1 mod 19.

    What should be added to 2122 so that it is divisible by 23?

    we know that 2122 = 1 mod 23 as 23 is a prime number and HCF(21, 23) = 1. (Fermat’s Theorem)

    So we must add 22 to the number to make it divisible by 23.

    What are the last two digits of 79121?

    Don't worry, last two digits of a number is it's remainder only when it is divided by 100. That means you are to find the remainder of the number with 100.

    As 100 and 79 are co-prime, we can use Euler's th. Also phi(100) = 40.

    So 7940 = 1 mod 100

    and 79121 = 79 mod 100.

    What if Number and divisor are not co-prime i.e. HCF(M, N) is not equal to 1?

    No issues: Just take the HCF of the number and divisor our and fond remainder of remaining number with remaining divisor.

    Final answer will be HCF times the remainder obtained by remaining number and remaining divisor.

    Find the remainder when 232 is divided by 32.

    Don’t get bewildered by the trap. Answer is zero. :D

    Find the remainder when 312 is divided by 12.

    Now HCF of number and divisor is 3.

    So the required remainder will be 3*[311 mod 4] = 3(-1) mod 12 = 9 mod 12.

    MOD - We talked something about the phrase/operation earlier also. Let’s repeat them and try to be more familiar with it.  When I say 31 = 3 mod 7, that mean 31 is a number of the form 7a + 3 OR in other words, we can also say 31 leaves remainder 3 when divided by 7.  So just to avoid this long sentence every time, we use this internationally used term 'mod'.

    Remember that term before 'mod' doesn't always give the remainder. It tell us only the form of the number e.g. 5 mod 7 = 7a + 5 = 7a + 7 - 2 = 7(a + 1) - 2 = -2 mod 7.

    Hope you got it. Now observe one more thing that we can also write:

    5 mod 7 = -2 mod 7 = -9 mod 7 = -16 mod 7 and also 5 mod 7 = 12 mod 7 = 19 mod 7 = 26 mod 7.

    That means you can add/subtract the divisor any number of times from the number before 'mod' and it'll not change the form of the number.

    Also if we say that 21N = 7 mod 8

    That means 7*3N = 7*1 mod 8

    Or 3N = 1 mod 8

    Or 3N = (1 + 8 ) mod 8 = 9 mod 8 = 3*3 mod 8

    That means N = 3 mod 8.

    Read every step carefully.

    Now let’s use this in remainder problems

    If 20N is divisible by 7, find the remainder when N + 20 is divided by 7.

    It’s simple to get that N = 0 mod 7

    So N + 20 = (0 + 20) mod 7 = 20 mod 7 = (20 – 7 – 7) mod 7 = 6 mod 7.

    If 37N = 5 mod 41, find the remainder when N is divided by 41.

    37N = 5 mod 41

    (37 - 41) N = -4N = 5 mod 41

    4N = -5 mod 41 = (-5 + 41) mod 41 = 36 mod 41 = 4*9 mod 41

    N = 9 mod 41.

    Solve one more to get hold of concept.

    Find the smallest natural number N such that 13N = 17 mod 19.

    13N = 17 mod 19

    (13 - 19)N = (17 - 19) mod 19

    -6N = -2 mod 19

    3N = 1 mod 19 = (1 - 19) mod 19 = -18 mod 19 = 3(-6) mod 19

    N = -6 mod 19 = 13 mod 19.

    Do 5 more problems on this.

    Find smallest N such that

    i. 31N = 5 mod 17

    II. 23 N = 15 mod 19

    III. N(N+1) = 2 mod 20

    iv. 14N = 3 mod 23

    v. 213N = 102 mod 315

    Solutions:

    i. 31N = 5 mod 17

    -3N = -12 mod 17

    N = 4 mod 17.

    ii. 23N = 15 mod 19

    (23 - 19)N = (15+19+19+19) mod 19

    4N = 72 mod 19

    N = 18 mod 19.

    iii. N(N+1) = 2 mod 20

    N(N+1) = 1(1 + 1) mod 20

    N = 1 mod 20

    BUT also, N(N+1) = (2 + 20 + 20) mod 20 = 6(6 + 1) mod 20

    So N = 6 mod 20 is also possible.

    Also, N(N + 1) = (2 + 180) mod 20 = 13(13 + 1) mod 20

    So N = 13mod 20 is also possible.

    Similarly N(N + 1) = (2 + 340)mod20 = 18(18 + 1) mod 20

    So N = 18 mod 20 also possible.

    That means there four possible values of N i.e. 1, 6, 13, 18 mod 20. But smallest is of course 1.

    iv. 14N = 3 mod 23

    -9N = 3 mod 23

    3N = -1 mod 23 = -24 mod 23

    N = -8 mod 23 = 15 mod 23.

    v. 213N = 102 mod 315

    -102N = 102 mod 315

    N = -1 mod 315

    N = 314 mod 315

    We will do a better problem now.

    Find the remainder when 3939 is divided by 41.

    Using Euler’s we know that 3940 = 1 mod 41 as HCF(39, 41) = 1

    Let’s say 3939 = x mod 41.
    3940 = 39 × 3939 = 1 mod 41
    39x = 1 mod 41
    -2x = -40 mod 41
    x = 20 mod 41.

    Next type of problems: If divisor is composed of more than one prime number, then we can break it into its co-prime factors and find the individual remainders and then combine them.

    Find the remainder when 277 is divided by 77.

    You can directly use phi(77) = 60. But then it’ll be lengthy to find the remainder of 217 with 77.

    So it’s better to find the remainder individually with 7 and 11 and then combine them.

    Now 277 = [(26)12][25] = 25 mod 7 = 4 mod 7. (as phi(7) = 6 and HCF(2, 7) = 1)

    And 277 = [(210)7][27] = 27 mod 11 = -4 mod 11. (as phi(11) = 10 and HCF(2, 11) = 1)

    Now comes the big problem: HOW TO COMBINE THESE REMAINDERS TO GET THE REMAINDER WITH 77.

    There are three different methods you can do that.

    First is COMMON TERM FINDING method

    Write the sequence of numbers 4 mod 7 i.e. 4, 11, 18, 25, 32, 39, …… and

    -4 mod 11 i.e. -4, 7, 18, 29, ……………

    AND we are to just find the smallest common number which is there in both the sequences. 18 it is.

    Second is USING EQUATIONS

    Write the equation for remainder R = 7a + 4 = 11b – 4

    i.e. 7a = 11b – 8 = 7b – 7 + 4b – 1

    As LHS is divisible by 7, RHS must be.

    So we need to find the smallest b such that 4b – 1 is divisible by 7 and voila... b = 2 satisfies.

    That means R = 11*2 – 4 = 18.

    Third is imported one CHINESE REMAINDER THEOREM

    First step: The two divisors, to be combined, should be co-prime

    Second step: Write an equation using the two divisors such that the difference between the integral multiple of two divisors is 1.

    So in this case we get 11 × 2 – 7 × 3 = 1

    Now remainder is obtained by multiplying an extra term with each term of LHS i.e.remainder of the other divisor.

    So it becomes [11 × 2 × 4 – 7 × 3 × (-4)] mod 77 = (88 + 84) mod 77 = (11 + 7) mod 77 = 18 mod 77.

    How many four digit numbers exist such that when divided by 7, 9 and 11 one gets the remainders of 2, 3 and 4 respectively.

    7a + 2 = 7a + 2 - 350 = 7a - 348 9b + 3 = 9b + 3 - 351 = 9b - 348 11c + 4 = 11c + 4 - 352 = 11c - 348 So N = 7 × 9 × 11d - 348 = 693d - 348 = 693d + 345

    Here remainders from the three numbers have difference of 1. So I just need to found their multiple with gap of 1 as above and job is done.

    And it is also not time consuming as multiple of 11 should give digit sum 1 as it had to be one more than multiple of 9 and multiple of nine will always give digital sum 9 or 0. So 11 (digital sum 2) should be multiplied with a number with digital sum 5 i.e. 5, 14, 23, 32, 41, ...etc. Automatically number one less than this will be multiple of 9. So I just need to check whether number one more less than this multiple of 7 or not.....

    General divisibility rules

    an + bn is divisible by a + b if n is an odd natural number.
    an – bn is divisible by a + b if n is an even natural number.
    an – bn is divisible by a – b if n is any natural number.
    an + bn + cn + … is always divisible by (a + b + c + …) if a, b, c, …are in AP and n is an odd natural number.

    P(x) is divisible by (x - a) iff P(a) = 0

    P(x) gives remainder P(a) when divided by (x - a)

    Any (p - 1) digit repunit number is always divisible by p where p is a prime number greater than 5.

    I can go on forever with this. But I’ll have to stop now. :)

     



  • None of the article has explanations to the concept . You are stating the concept . There is no answer to why ? But only shortcuts which has no meaning .


  • Being MBAtious!


    @Siddharth-Jain Hi Siddharth, there are enough of articles that deal with the concepts and the articles like this are mostly meant for practice and fine tuning the methods. So it is a pre requisite to build the base before solving similar articles. If you are looking for remainder theorem concepts you can read https://www.mbatious.com/topic/61/remainder-theorem (might help)


Log in to reply
 

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