Remainder Theorem - Anubhav Sehgal, NMIMS Mumbai


  • NMIMS, Mumbai (Marketing)


    Prerequisite : A remainder problem is often solved using symbols such mod and % which simply refer to the remainder left after say, 19 mod 4 (i.e 19 / 4) is carried out. Hence 19 mod 4 = 19 % 4 = 3

    There are several important theorems and patterns that exist and are often found useful while solving problems on remainders. I will try to present and exemplify each of them and help the readers achieve complete clarity. Let's begin with the first on the to-do list :

    Euler's Remainder Theorem

    Statement : N^E(n) mod n = 1 , provided N and n are co-primes.
    Symbols : E(n) is called the Euler number and is given as follows : If n = a^p * b^q * c^r *... in its prime factorization form Then, E(n) = n * (1 - 1/a)(1 - 1/b)(1 - 1/c)..
    example : 100 = 2^2 * 5^2 => E(100) = 100 * (1 - 1/2) * (1 - 1/5) = 40
    Usage : Find the remainder when 5^26 is divided by 21.
    Since 5 and 21 are co-primes, we find E(21) = 21 * (1 - 1/3)(1 - 1/7) = 12
    5^26 mod 21
    5^12 * 5^12 * 5^2 mod 21
    1 * 1 * 25 mod 21 = 4 [ Remainders are multiplicative. You can multiply remainders of different components of the same number provided they are disjoint i.e there is no overlapping]

    So this theorem in essence helps you reduce powers and find remainders of otherwise very large numbers and brings it down to a small remainder problem. It may be used as a part of a bigger problem sometimes as well where in you may need to apply further process to solve the problem.

    Fermat's Remainder theorem :

    Special case of Euler's Remainder theorem when n = a prime number, p.
    E(p) = p - 1 always for any prime.
    So this theorem states : N^(p - 1) mod p = 1 if N, p are co-primes

    Wilson Remainder Theorem

    Results and Extensions :
    If p is a prime number then, (p - 1)! mod p = (p - 1) or -1
    (p - 2)! mod p = 1
    AND
    If n is a composite number, then (n - 1)! mod n = 0 for all n except 4 because 3! mod 4 = 2

    Usage : Find the remainder when 19! is divided by 23.
    We know that 21! mod 23 = 1
    21 * 20 * 19! mod 23 = 1 - 2 * -3 * 19! mod 23 = 1 [Negative remainder = Positive Remainder by same divisor - Divisor] 6 * r mod 23 = 1
    r = 4 satisfies. Hence, 19! mod 23 = 4

    Chinese Remainder Theorem (CRT)

    Statement : If n can be written as a product of co-primes say a,b,.. then,
    N mod n = R(say)
    We find, N mod a = r1 ; N mod b = r2 ; ...
    Then R = common term satisfying : p * a + r1 = q * b + r2 = ... where p,q are variables.

    An example will clear it up more. So let's take one in the Usage of this theorem..

    Usage : Find the remainder when 21! is divided by 115
    We know that 115 = 23 * 5
    21! mod 23 = 1 [ By Wilson's theorem ]
    So, 21!^5 mod 23 = 1
    Also, 21! mod 5 = 0
    => We write :
    23a + 1 = 5b
    5(4a) + 1 + 3a = 5b
    Take mod 5 on both sides now, (3a + 1) mod 5 = 0
    a = 3 satisfies. => 23(3) + 1 = 70 = Remainder
    You could also found b and put it in 5b and you would have got the same answer but taking up the side with bigger divisor is advisable as it makes calculation easier


Log in to reply
 

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