# Modulus of large(ish) numbers

Original problem: what is $800^{35} \bmod 11$?

I was able to use Euler's Theorem, $a^{\varphi(n)}\equiv1\space(\bmod\space n)$, to boil the problem down to $800^{35} \equiv 800^5\space (\bmod\space 11)$.

My issue is that $800^5$ is still a pretty big number to work with (won't fit on my calculator screen) and I would like to know how to this by hand. How should I proceed from here?

-
reduce 800? We have $800 \equiv 30 \equiv 8 \pmod {11}$. So $800^{35}\equiv 8^5\pmod{11}$. –  martini Oct 14 '12 at 0:36
$800^n$ is congruent to $8^n$ mod $11$ since $800$ is congruent to $8$ mod $11$. –  Grumpy Parsnip Oct 14 '12 at 0:37

We have $800 \equiv 30 \equiv 8 \pmod {11}$. So $800^{35}\equiv 8^5\pmod{11}$. As $8 = 2^3$, $8^5 = 2^{15} \equiv 2^5 = 32 \equiv 10 \pmod{11}$.
How did you get $800\equiv30$ and $30\equiv8$? Also, is the raised 5 carried over from the result of Euler's theorem? –  James Oct 14 '12 at 0:53