Solving Remainder Based Questions

Ok. Write it down. The next time you see a question on remainders while giving a test, you would feel really lucky. Because I am going to describe some very useful methods that can be used to this end.

Let us start with the basic ones - (note - in all the formulas below, x mod y means the remainder obtained after dividing x by y)

ab mod x = (a mod x) * (b mod x)

If a mod x = 1, then a^k mod x = 1 for any integer k > 1

If a = lx + 1, then a^k mod x = 1 for all k > 1

If a = lx -1, then a^k mod x = (-1)^k for all k > 1

Let us cover some examples

5^43 mod 13 = ?

Whenever you see such questions, try to get the base of the exponent as close to a multiple of the diviser as possible. We see that 5^2 = 26 - 1. Hence,

5^43 mod 13 = 5. 5^42 mod 13 = 5 mod 13 . 25^21 mod 13 = 5.(-1)^21 mod 13 = -5 mod 13 = 8 mod 13

The ones described above are the basic formulae related to modulo arithematic. Let now get a bit deep into it. We will cover two theorems here:

1) Chinese Remainder theorem
2) Euler's extension of Fermat's theorem

Chinese Remainder theorem: For a specific number N, if N mod a = k1, N mod b = k2, such that a and b are co-prime (gcd(a,b) = 1) then all solutions of M mod a = k1 and M mod b = k2 in the set of the natural numbers are equivalent modulo ab.

Too tough to understand? Well, it's not as tough if we take an example:

Let us say we have to find the remainder when

66666... 1730 times is divided by 45.

Since it is difficult to find the remainder when the number is divided by 45, we take the divide and conquer approach.

First divide 66666... 1730 times by 5, remainder is 1
Divide 66666.. 1730 terms by 9, remainder is 6*1730 mod 9 = 6*2 mod 9 = 3

Chinese remainder theorem states that if we are able to find a number < 45 that satisfies the above two conditions, then that number itself is the remainder when the big number is divided by 45. Let's list all numbers which are give a remainder of 3 when divided by 9. They are:

3,12,21 <- while listing, we have arrived at a number which leaves a remainder of 1 when divided by 5. And this number itself is the answer! Note: To increase your speed, you should start listing based on the greater of the two numbers, which in this case is 9.


Euler's extension of Fermat's theorem:

If a and n are co-prime (gcd(a,n)=1), then a^phi(n) mod n = 1, where phi(n) is the Euler Totient function of n, which can be obtained as n(1-1/p1)(1-1/p2)...(1-/1pn); p1, p2...,pn being the prime factors of n

OK. This also looks a bit convoluted. Let's take up an example instead.

What are the last 2 digits of 3^768?

We basically need to find 3^768 mod 100 here. We have phi(100) = 100(1-1/2)(1-1/5) = 40 (as 2,5 are the prime factors of 100).

Now since 3^40 mod 100 = 1, we have 3^768 mod 100 = (3^40)^19 mod 100 . 3^8 mod 100

= 1 mod 100 * 3^8 mod 100

= 3^8 mod 100 = 81^2 mod 100 = (100-19)^2 mod 100 = 19^2 mod 100 = 61.

Hope some of the concepts are clear to you by now. I will be updating this post as I post solutions to questions on remainders. If you have any, please send them across.