Find the Hundreds Digit of 2011^2011

Posted: October 20, 2022 in Mathematics
Tags: , , , ,
0

This is problem 23 of AMC 10B in 2011. So, here is the problem:

\text{Find the hundreds digit of } 2011^{2011}

I will present three solution here. The first one uses Chinese Remainder Theorem, which is the slowest, takes about 5 to 10 minutes. The second solution I will just use Euler Phi function, which is quicker, about 3 minutes. And the third solution I will use the trick of using Binomial Theorem, which is super fast, takes about 10 seconds.

SLOWEST method:

By Chinese Remainder Theorem, we have

\displaystyle N = a_1 b_1 M_1 + a_2 b_2 M_2 \pmod{M} \qquad \text{where } M_1 = \frac{M}{M_2} \text{ and } M_2=\frac{M}{M_1}

We have N = 11^{2011}, M = 1000, M_1 = 8, \text{ and } M_2 = 125.

We need to find a_1, b_1, a_2, b_2

2011^{2011} \equiv 11^{2011} \pmod{1000}

Since (11, 8)=1 \text{ and } \phi(8) = 8\cdot\dfrac{1}{2} = 4, then

11^{2011} \equiv 11^3 \equiv 27 \equiv 3 \pmod{8}

So, a_1 = 3

To find b_1,

125b_1 \equiv 1 \pmod{8}

5b_1 \equiv 1

b_1 \equiv 5

Next, we will find a_2,

Since (11,125)=1 \text{ and } \phi(125) = 125\cdot \dfrac{4}{5} = 100, then

11^{2011} \equiv 11^{11} \pmod{125}

11^2 \equiv 121 \equiv -4

11^4 \equiv 16

11^8 \equiv 256 \equiv 6

11^3 \equiv -44

\Rightarrow 11^{11} \equiv 6 \cdot (-44) \equiv -264 \equiv 111

So, a_2 = 111

Next, we are going to find b_2

8b_2 \equiv 1 \pmod{125}

8b_2 = 125k + 1

0 \equiv 5k+1 \mod{8}

5k \equiv 7 \mod{8}

k \equiv 35 \equiv 3 \mod{8}

\therefore b_2 = \dfrac{125\cdot3+1}{8} = 47

Hence,

2011^{2011} \equiv 11^{2011} \equiv 3 \cdot 5 \cdot 125 + 111 \cdot 47 \cdot 8 \equiv 875 + 736 \equiv 611 \pmod{1000}

Therefore, the hundreds digit is 6.

STANDARD Number theory method:

Note that (11, 2011) = 1, hence

\displaystyle 11^{\phi(1000)} \equiv 1 \pmod{1000} \qquad \text{where } \phi(n) = \prod_{p \mid n} \frac{p-1}{p}

Now,

\phi(1000) = 1000\cdot\dfrac{1}{2}\cdot\dfrac{4}{5} = 400

then,

2011^{2011} \equiv 11^{2011} \equiv 11^{400\cdot5+11} \equiv 11^{11} \pmod{1000}

11^2 \equiv 121

11^3 \equiv 121(1+10) \equiv 121 + 210 \equiv 331

11^4 \equiv 331 + 310 \equiv 641

11^5 \equiv 641 + 410 \equiv 51

11^{10} \equiv 51^2 \equiv (50+1)^2 \equiv 500 + 100 + 1 \equiv 601

11^{11} \equiv 601 + 10 \equiv 611

Therefore the hundreds digit is 6.

SUPER FAST Method:

By Binomial Theorem,

2011^{2011} = (1 + 2010)^{2011} = 1+2011\cdot 2010 + \binom{2011}{2} 2010^2 + \binom{2011}{3} 2010^3 + \cdots

\equiv 1+ 11\cdot10 + \dfrac{2011\cdot2010}{2}\cdot 10^2 \pmod{1000}

\equiv 1 + 110 + 11 \cdot 5 \cdot 100 \equiv 611

Therefore the hundreds digit is 6.

Leave a comment