Online Course Discussion Forum

Math Challenge II-A Number Theory

 
 
Picture of Neo Liang
Math Challenge II-A Number Theory
by Neo Liang - Saturday, August 17, 2019, 4:12 PM
 

Lecture 10, problem 10.10

Can you tell me the solution and the answer?

 
Picture of David Reynoso
Re: Math Challenge II-A Number Theory
by David Reynoso - Monday, August 19, 2019, 2:56 PM
 

We are looking to find $2011^{2011} \pmod{1000}$, since we want the hundreds digit.

First note $2011^{2011} \equiv 11^{2011} \pmod{1000}$. Using the extension to Fermat's Little Theorem, since $\phi(1000) = 1000 \cdot \left(1 - \dfrac{1}{2} \right) \left(1 - \dfrac{1}{5}\right) = 400$, we have $11^{400} \equiv 1 \pmod{1000}$, so $11^{2011} \equiv 11^{400 \cdot 5 + 11} = 11^{11} \pmod{1000}$.

To find $11^{11} \pmod{1000}$, since $1000 = 2^3 \times 5^3$, we can find $11^{11} \pmod{2^3}$ and $11^{11} \pmod{5^3}$. Since $11 \equiv 3 \pmod{8}$ and $11^2 \equiv -4 \pmod{125}$,  is not difficult to see that $11^{11} \equiv 3 \pmod{8}$ and $11^{11} \equiv 111 \pmod{125}$.

Between $1$ and $1000$ the only number that is $3 \pmod{8}$ and $111 \pmod{125}$ is $611$, so the last three digits of the number are $611$, with hundreds digit $6$.