Numbers are like infinite steps on the sand always leaving a known impression behind. Let's dive into this ocean and unlock the mystery of remainders...
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 [See image]
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 115We 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.
Go through the process of solving carefully as well and practice. This process of multiple steps would become a one liner for you with time :)
That's about it as far as major theorems are concerned and this much should be enough to absorb in one go. So we will look into a second part where we discuss some other important generalizations and patterns that are used to solve remainder problems.
Rate,Like and Share the work if you like it as always. Leave comments for any doubts or reviews.
Cheers!
AS
No comments:
Post a Comment