modular arithmetic with large numbers

Posted: September 24, 2012 in Mathematics
Tags: , , , ,

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,

$14=3\cdot4+2$

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

$14\equiv2\quad\mbox{ mod } 3$

Now this seems easy everyone can do it.  But what if someone asks you to find a remainder when $2^{99}$ 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 $2^{99}$ 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

$2^4\equiv16\equiv1 \quad\mbox{ mod }15$

then we have

$2^{99} \equiv 2^{4\cdot24+3} \equiv (2^4)^{24}\cdot2^3 \equiv 1\cdot8 \equiv 8\quad\mbox{ mod }15$

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 $32141^{43210}$.  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 $32141^{43210} \quad\mbox{ mod } 100000$

<< 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,

$100000=10^5=2^5 5^5=32 \cdot 3125$

then we find their Euler’s phi function,

$\phi(32)=16, \qquad \phi(3125)=2500$
By the Euler’s Theorem, if $(a,n)=1$, then

$a^{\phi(n)} \equiv 1 \mbox{ mod } n$

Since 2 and 5 do not divide 32141 we have,

$32141^{16} \equiv 1 \quad\mbox{ mod } 32$

$32141^{2500} \equiv 1 \quad\mbox{ mod } 3125$

then

$32141^{43210} \equiv 32141^{10} \quad\mbox{ mod } 32$

Since $32141=32\cdot1004+13$

We have $32141^{10} \equiv 13^{10} \quad\mbox{ mod }32$

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

$13^2\equiv169\equiv9$

$13^4\equiv81\equiv17$

$13^8\equiv289\equiv1\quad\mbox{ mod }32$

then

$13^{10} \equiv 13^8\cdot13^2 \equiv 1\cdot9 \equiv9\quad\mbox{ mod }32$

Therefore,

$32141^{43210} \equiv 32141^{10} \equiv 13^{10} \equiv 9 \quad\mbox{ mod }32$

similarly we have,

$32141^{43210} \equiv 32141^{710} \equiv 891^{710} \equiv 2651 \quad\mbox{ mod }3125$

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

$x=32141^{43210}, M=100000$

$a_1=9, m_1=32, a_2=2651, m_2=3125$

with $x\equiv a_1b_1\frac{M}{m_1}+a_2b_2\frac{M}{m_2} \mbox{ mod } M$

we need to solve

$3125b_1 \equiv 1 \mbox{ mod } 32$

and

$32b_2 \equiv 1 \mbox{ mod } 3125$

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

$3125b_1\equiv1\mbox{ mod }32$

$21b_1\equiv1\mbox{ mod }32$

then apply the Euclidean Algorithm,

$32=21+11$

$21=11+10$

$11=10+1$

then we work it backward,

$1=11-10=32-21-(21-11)=32-2(21)+32-21=2(32)-3(21)$

hence,

$b_1 \equiv -3 \equiv 29 \mbox{ mod } 32$

Similarly,

$b_2 \equiv 293 \mbox{ mod }3125$

$\therefore 32141^{43210} \equiv 9(29)(3125)+2651(293)(32) \equiv 71401 \mbox{ mod }100000$

Remark:

There is also an easier way, since

$9 \mbox{ mod } 32 = 2651 \mbox{ mod } 3125$

then there exists an $n\in\mathbb{Z}$

$x=3125n+2651=9 (\mbox{mod }32)$

$21n+27=9$

$21n=-18$

$21n=14$

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

$3n=2$

Since $66=2(32)+2$

$n=22$

$\therefore x=3125(22)+2651=71401$

<< 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.

$\phi(100000)=16\cdot2500=40000$

$\therefore 32141^{43210} \equiv 32141^{3210}\mbox{ mod }100000$

Now apply Binomial theorem,

$(1+32140)^{3210} \qquad \mbox{mod }100000$

$=1+\binom{3210}{1}32140+\binom{3210}{2}32140^2+\binom{3210}{3}32140^3+\binom{3210}{4}32140^4$

Since $8|3214^4$ and $3|321$,

$\displaystyle\binom{3210}{4}32140^4=\frac{3210\cdot3209\cdot3208\cdot3207}{4\cdot3\cdot2}32140^4=0\mbox{ mod }100000$

$\displaystyle=1+321\cdot3214\mbox{ (mod }1000)\cdot100\\+\frac{321\cdot3209}{2}\cdot3214^2\mbox{ (mod }100)\cdot1000\\+\frac{321\cdot3209\cdot3208}{3\cdot2}\cdot3214^3\mbox{ (mod }10)\cdot10000$

$=1+321\cdot214\mbox{ (mod }1000)\cdot100\\+21\cdot9\cdot14\cdot7\mbox{ (mod }100)\cdot1000\\+7\cdot9\cdot4\cdot4^3\mbox{ (mod }10)\cdot10000$

$=171401=71401 \mbox{ mod } 100000$