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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s