In elementary school, we learn division and quite often when a number is divided by a divisor we don’t exactly get the answer without remainder. For example, when a number 14 is divided by 3 then the quotient is going to be 4 with the remainder 2. Because of the following,

Now if we translate this into modular arithmetic, it becomes:

Now this seems easy everyone can do it. But what if someone asks you to find a remainder when is divided by 15? If you do it the way a grade 4 student does, you will first of all need to compute the monster which is quite impossible for any mortals to calculate by hand and even with a scientific calculator. And not to mention dividing that huge number by 15 which will take probably another life time to do it by hand. Fortunately there is a way to compute all that stuffs. Since

then we have

Now this seems easy isn’t it? I am sure everyone can do it. Let’s do something more interesting. I saw this problem last week on a forum. Find the last five digits of . Ok, this is an interesting one 🙂 So I shall give two different ways to solve this for the readers. Notice that this is the same as asking to find

**<< Method 1 >>**

In this solution, I am going to apply Euler’s Theorem and Chinese Remainder Theorem.

The reason that Chinese Remainder Theorem is necessary in here is because the number 100000 isn’t prime. And we can factor 100000 into two numbers which are relatively prime to each other as,

then we find their Euler’s phi function,

By the Euler’s Theorem, if , then

Since 2 and 5 do not divide 32141 we have,

then

Since

We have

Here we can use “the power of 2” trick to reduce this since,

then

Therefore,

similarly we have,

Now we apply the Chinese Remainder Theorem, (see link for explanation)

with

we need to solve

and

I will do the first one, and leave the second for reader.

then apply the Euclidean Algorithm,

then we work it backward,

hence,

Similarly,

*Remark:*

There is also an easier way, since

then there exists an

Since 7 and 32 are relatively prime, we can divide both sides by 7

Since

**<< Method 2 >>**

This method here involves Binomial Theorem, which is faster in this case.

First, we will use a trick from *Method 1* to reduce the power 43210 to 3210.

Now apply Binomial theorem,

Since and ,