Remainder Theorem


  • Being MBAtious!


    Remainder theorem is a very important topic in number system and can be learnt easily. We will try to learn some interesting concepts regarding remainders with examples. Here we go!

    Definition of remainder

    If a and d are natural numbers, with d # 0, it can be proved that there exist unique integers q and r, such that a = qd + r and 0 ≤ r < d. The number q is called the quotient, while r is called the remainder.

    Dividend = Divisor × Quotient + Remainder.

     if r = 0 then we say that a is perfectly divisible by d or d is a factor of a. For example, we say 8 is a factor of 40 because 40 leaves a remainder 0 with 8.

    By definition remainder cannot be negative.

    Now just to give an example, 17 = 3 * 5 + 2, which means 17 when divided by 5 will give 2 as remainder. Well that was simple!

    Find Remainder[ (12 * 13 * 14) / 5 ]

    Remainder [ (12 * 13 * 14) / 5 ]

    = Remainder [2184/5] = 4. But this method is not the right one for us :)

    In order to find the remainder of an expression find the individual remainder and replace each term with the respective remainders.

    Eg: Remainder[(100 + 30 * 4 - 8 ) / 7]

    = Remainder[(Remainder[100/7] + Remainder[30/7] * Remainder[4/7] - Remainder[8/7] ) / 7 ]

    = Remainder[(2 + 2 * 4 - 1)/7] = Remainder[9/7] = 2

    In the above case 12, 13 and 14 will give remainders 2, 3 and 4 respectively when divided by 5. So replace them with the respective remainders in the expression and find the remainder again.

    Remainder [ (12 * 13 * 14) / 5 ] = Remainder[(2 * 3 * 4) / 5] = Remainder[ 24 / 5 ] = 4.

    Note:

    One common mistake while dealing with remainders is when we have common factors in both dividend and divisor. Example, what is the remainder when 15 is divided by 9

    15 / 9 is same as 5 / 3, remainder 2. Correct? No 15/9 will give a remainder of 6.

    Where we slipped?

    Always remember that if we find remainder after cancelling common terms make sure we multiply the remainder obtained with the common factors we removed.

    In previous case we will get correct answer (6) when we multiply the remainder obtained (2) with the common factor we removed (3).

    What is the remainder of 1421 * 1423 * 1425 when divided by 12 ? ( CAT 2000 )

    1421, 1423 and 1425 gives 5, 7 and 9 as remainders respectively when divided by 12.

    Remainder [ (1421 * 1423 * 1425 ) / 12 ] = Remainder [ (5 * 7 * 9) ] / 12, gives a remainder of 3.

    Find the reminder when 1! + 2! + 3! + . . . . .. . .. 99! + 100! is divided by the product of first 7 natural numbers

    From 7! the remainder will be zero. Why ?  because 7! is nothing but product of first 7 natural numbers and all factorial after that will have 7! as one of the factor. so we are concerned only factorials till 7!, i.e, 1! + 2! + 3! + 4! + 5! + 6!

    1! + 2! + 3! + 4! + 5! + 6! = 873 and as 7! > 873 our remainder will be 873

    What is the remainder when 64999 is divided by 7? (GMAT Type Question)

    Many of us get intimidated with such numbers, always remember that the key to crack quant is a strong hold of basic concepts.

    Remainder [64999 / 7 ] = Remainder[ 64 * 64 * …. 64 (999 times) / 7 ]

    Remainder[64/7] = 1, hence Remainder [64999 / 7 ] = Remainder [ 1 999 / 7 ] =  1

    What is the remainder when 444444 ^ 444 is divided by 7 ? (GMAT Type Question)

    Remainder[444/7] = 3

    Remainder[ 444 444 ^ 444  / 7 ] = Remainder [ 3 444 ^ 444 / 7 ]

    = Remainder [ ( 3) 222 ^ 444 / 7 ] = Remainder [ 2222 ^ 444 / 7 ] ( As Remainder [ 32 / 7 ] = 2 )

    = Remainder [ ( 23 ) 74 ^ 444  / 7] =  Remainder [ 1 74 ^ 444  / 7 ] = 1 ( As Remainder [ 23 / 7 ] = 1 )

    Concept of negative remainder

    We saw earlier that by definition remainder cannot be negative. But considering negative remainder is a very useful exam trick.

    For example,

    What is the remainder when 211 divided by 3?

    The easiest method for this one will be using the concept of negative remainders.

    Here 2 when divided by 3 gives a remainder of -1. (Say)

    2 = 3 * 1 + (-1), remainder is -1, which is theoretically incorrect but let’s cheat!

    So we are asked to find (-1) * (-1) * … 11 times divided by 3.

    Which is Remainder[-1/3] = -1.

    Whenever you are getting negative number as a remainder, make it positive by adding the divisor to the negative remainder.

    Here required answer is 3 + (-1) = 2.

    Remainder when (41 * 42) is divided by 43

    Use negative remainder concept,

    Remainder [ 41 * 42 / 13 ] = Remainder[(-2) * (-1) / 43 ]( as 41 = 43 * 1 – 2 and 42 = 43 * 1 – 1)

    = Remainder [ 2 /43 ] = 2 (here we got a positive remainder itself, so no need of correction)

    Some useful concepts while dealing with remainder are given below.

    Remainder[(ax + 1)n / a] = 1 for all values of n.

    Find the remainder when 10099 is divided by 11

    Remainder[10099 / 11 ] = Remainder[(11* 9 + 1)99 / 11] = 1.

    Remainder[(ax - 1)n / a ] = 1 when n is even

    Remainder[(ax - 1)n / a ] = (a-1) when n is odd.

    Find the remainder when 21875 is divided by 17.

    Remainder[21 / 17] = 4, so we need to find Remainder[4875/ 17]

    42 = 16 = (17 – 1), we can write the expression as Remainder[(42)437 * 4 / 17]

    = Remainder[(17 – 1)437 * 4 / 17] = Remainder[(17-1) * 4 / 17] = Remainder[64 / 17] = 13.

    Remainder[(an + bn) / (a + b) ] = 0 when n is odd.

    Remainder[(2101 + 3101) / 5 ] = 0

    What is the remainder when 1523 + 2323 is divided by 19 ? ( CAT 2004 )

    1523 + 2323 is divisible by 15 + 23 = 38 ( as 23 is odd).

    So Rem[(1523 + 2323)/19] = 0

    Remainder[(an + bn + cn + ...) / (a + b + c + ...) ] = 0 if ( a + b + c + ... are in Arithmetic progression and n is odd

    What is the remainder when 163 + 173 + 183 + 193 is divided by 70 ?  ( CAT 2005 )

    Apply the above funda. Here n =3 ( odd ), 16 + 17 + 18 + 19 = 70 and 16,17,18 and 19 are in AP. Remainder is 0

    Remainder[(an - bn) / (a + b) ] = 0 when n is even.

    Remainder[(5100 – 2100) / 7] = 0

    Remainder [(an - bn) / (a - b) ] = 0

    Now we can say Remainder[(10175 – 7675) / 25] = 0 in no time..!

    The remainder when f(x) = a + bx + cx2+ dx3+ … is divided by (x-a) is f(a)

    Rem [(3x2 + 4x + 1) / (x-2)] = f(2) = 3 * 22 + 4 * 2 + 1 = 21

    Cyclic property of remainders

    Sometimes it is easy to find the remainder by using the cyclic property of remainders, remainders forming a pattern.

    As a thumb rule if we divide pn with q, the remainder will follow a pattern.

    For example,

    Remainder [ 21 / 3 ] = 2, Remainder [ 22 / 3 ] = 1, Remainder [ 23 / 3 ] = 2, Remainder [ 24 / 3 ] = 1 and so on. 

    Pattern repeats in cycles of 2. Remainder [ 2n / 3 ] = 2 when n is odd and 1 when n is even.

    With this information, we can find Remainder [ 23276 / 3 ] = 1 very quickly.

    One more, Remainder [ 91 / 11 ] = 9, Remainder [ 92 / 11 ] = 4, Remainder [ 93 / 11 ] = 3 , Remainder [ 94 / 11 ] = 5

    Remainder [ 95 / 11 ] = 1, Remainder [ 96 / 11 ] = 9, Remainder [ 97 / 11 ] = 4, Remainder [ 98 / 11 ] = 3 

    Pattern repeats in cycles of 5. So if we are asked to find Remainder [ 9100 / 11 ],  we know it is 1. (100 is in the form 5n and we know remainder for 5 is 1.. cool right ?)

    Note:

    Remainder [93/11] = Remainder [Remainder [92/11] * Remainder [92/11] ) / 11] = Remainder [ 4 * 9 / 11] = 3.

    This funda comes very handy in scenarios like this. Like we dont have to solve Rem [98 /11] because we already know Rem[94 /11] as 5..

    Rem [98 /11] = Remainder [ 9* 94 /11 ] =  Remainder [ (5 * 5) / 11 ] = 3

    Also, Remainder [97 /11] = Remainder [93 * 94 / 11 ] = Remainder [ ( 3 * 5 ) / 11 ] = 4 ( as Rem [93 /11] = 3 and Rem [94 /11] = 5 )

    What is the remainder when 7100 is divided by 4?

    Remainder[ 71 / 4 ] = 3, Remainder[ 72 / 4 ] = 1, Remainder[ 73 / 4 ] = 3, Remainder[ 74 / 4 ] = 1 and so on...

    Pattern repeats in cycles of 2.  Remainder [ 7n / 4 ] is 3 when n is odd and is 1 when n is even.

    7100 when divided by 4 gives a remainder of 1.

    (Same can be solved using other methods also)

    Find the remainder when 399^99 is divided by 7

    Find the pattern of remainder when 3n is divided by 7.

    Remainder [ 3/ 7 ] = 3, Remainder [ 32 / 7 ] = 2

    Remainder [ 33 / 7 ] = 6 (Don’t calculate Rem[33/7] we already have Rem[31/7] & Rem[32/7])

    Remainder [ 3/ 7 ] = 4 (using Rem[32/7])

    Remainder [ 3/ 7 ] = 5 (using Rem[33/7] and Rem[32/7] )

    Remainder [ 3/ 7 ] = 1 (using Rem[33/7])

    Remainder [ 3/ 7 ] = 3 (using Rem[33/7] and Rem[34/7] )

    Remainder [ 3/ 7 ] = 2 (using Rem[34/7])

    Pattern repeats in cycles of 6.  (We can do this easily from Euler’s theorem, as φ(7) = 6, hence Remainder [36/7] = 1. Explained just to get the idea of patterns in remainders)

    Now our task is to find Remainder [ 9999/ 6 ]

    Remainder [9999/6] = Remainder [399/6]

    Remainder [ 31 / 6 ] = 3, Remainder [ 32 /6 ] = 3, Remainder [ 33 / 6 ] = 3 and so on..!

    Hence 9999 can be written as 6n + 3.

    Remainder [ 399^99 / 7 ] = Remainder [ 3(6n + 3)/ 7 ]

    we have found out the pattern of 3 divided by 7 repeats in cycles of 6. So we need to find the Remainder [ 33 / 7 ]  to get the answer which is equal to 6

    Euler’s Remainder Theorem

    We say two numbers ( say a and b ) are co-prime to each other when HCF(a,b) = 1, i.e, no divisor divide both of them completely at the same time.
    Eg:  21 and 8 are co primes because they don't have any common factors except 1

    In number theory, Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n.

    Take n = 9, then 1, 2, 4, 5, 7 and 8, are relatively prime to 9. Therefore, φ(9) = 6.

    How to find Euler’s totient?

    Say n = P1x  P2x P3x ... ( where P1  P2, P3 ... are prime factors of n )

    φ(n) = n x (1 - 1/P1) x (1 - 1/P2) x (1 - 1/P3) x ....

    If n is prime then φ(n) = n - 1

    φ(100) = 100 x (1-1 / 2) x (1- 1 / 5) = 100 x 1 / 2 x 4 / 5 = 40

    φ(9) = 9 x (1 – 1/3) = 6

    Euler’s Remainder theorem states that for co prime numbers M and N,  Remainder [Mφ(N) / N] = 1

    Always check whether the numbers are co primes are not. Euler’s theorem is applicable only for co prime numbers

    What is the remainder when 21865 is divided by 17

    Remainder[21/17] = 4

    Remainder [ 21865/ 17 ] = Remainder [ 4865/ 17 ]

    4 and 17 are co prime numbers. ( A prime number is always coprime to any other number)

    φ(17) = 17 x ( 1 – 1 / 17) = 16.

    So Euler’s theorem says Remainder [ 416/ 17 ] = 1

    To use this result in the given problem we need to write 865 in 16n + r form.

    865 = 16 * 54 + 1, so 4865 can be written as 416 * 54  x 4

    Remainder[4865/17] = Remainder[ 416*54/17] * Remainder[4/17] = 1 * 4 =  4

    What is the remainder when 99999999 is divided by 23

    Remainder[99/23] = 7

    Remainder[99999999/23] = Remainder[7999999/23]

    7 and 23 are co prime numbers

    Here 23 is prime, so φ(23) = 22

    So by applying Euler's theorem we can say that Remainder[722/23] = 1

    In order to use this result in our problem we need to write 999999 in 22n + r form. Before rushing into dividing 999999 by 22, just think whether we have any better way to do that.  We know, 999999 = 22n + r , 0 ≤ r < 22.  999999 is divisible by 11 and so is 22. which means r is also a multiple of 11. Only numbers which are less than 22 and is a multiple of 11 is 11 and 0. But as 999999 is odd and 22n is even, r should be odd. so r = 11.  Saved our time right ? ;)

    999999 = 22n + 11

    Remainder[7999999/23] = Remainder[722n/23] * Remainder[711/23] = 1 * Remainder[711/23] = Remainder[72 * 5 * 7/23]

    = Remainder[ 35 * 7/23]  ( as Remainder[72/23] = 3 )

    = Remainder[33 * 32 * 7/23] = Remainder[4 * 9 * 7/23] = Remainder[28 * 9/23] = Remainder[45/23] = 22

    Find the remainder when 97 97 ^ 97 is divided by 11

    Remainder [97/11] = 9

    So, Remainder [9797^97/11] = Remainder [9 97^97/11]

    From Euler’s theorem, Remainder [910/11] = 1

    97 and 10 are again co primes. So φ(10) = 10 (1-1/2) (1-1/5) = 4

    Remainder [974/11] = 1

    97 = 4n + 1, So Remainder [9797/11] = Remainder [97/10] = 7

    Means 9797 can be written as 10n + 7

    Now our original question,

    Remainder [997^97/11] = Remainder [910n+7/11] = Remainder [97/11] = 4  :)

    Fermat’s little theorem

    Euler’s theorem says that if p is a prime numberand a and p are co-primes then aφ(p) / p always gives a remainder of 1.

    Now we know for any prime number p, φ(p) = p - 1

    Remainder of a( p – 1 )/ p is 1, which is Fermat’s little theorem

    We can derive other useful results like

    • Remainder of a/ p is a.
    • (ap – a) is always divisible by a.

    Wilson’s theorem

    Remainder[(p-1)! / p ] = (p-1), if p is a prime number.

    We can also derive some useful results like

    • Remainder of [(p-1)! + 1] / p is zero.
    • Remainder of (p-2)! / p is 1.

    Example:

    Remainder of [22!/23] = 22

    Remainder of [21!/23] = 1

    I hope the explanations are clear are correct. Please let me know if any concepts regarding remainders are missed out or incase of any errors.. Happy learning :)


Log in to reply
 

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