0
$\begingroup$

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?

  • 0
    $800^n$ is congruent to $8^n$ mod $11$ since $800$ is congruent to $8$ mod $11$.2012-10-14

1 Answers 1

4

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}$.

  • 0
    How did you get $800\equiv30$ and $30\equiv8$? Also, is the raised 5 carried over from the result of Euler's theorem?2012-10-14