Remainder Theorem - Anubhav Sehgal, NMIMS Mumbai

[anubhav_sehgal]

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