Online Course Discussion Forum
Math Challenge II-A Number Theory
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$.
Social networks