Finding the remainder of $823^{823}$ in the division by 11

Question

I wish to find the remainder $823^{823}$ in the division by $11$.

I used the Euler-Fermat theorem that tells that: $a^{\phi(n)} \equiv 1$ $(\mod n)$, whenever $(a,n) =1$ First, Euler- Fermat tells us that $a^{\phi(11)} \equiv 1 (\mod 11)$ whenever $a$ is coprime with to 11. Since 823 is prime, we have, $(823,11) = 1$. Now $823 \equiv 9 (\mod 11)$

But I don't know how to continue.. Because both $823$ and $11$ are prime ; do I have to use Fermat's little theorem?

Any help appreciated

Answer 1

Note that $$823^5\equiv 1 \mod 11$$ and then you can square the equation.

Answer 2

Note that you also have $823\equiv -2\mod11$, which will make calculating powers by hand easier. Now by lil' Fermat, $$823^{823}\equiv (-2)^{823\bmod 10}=-8\equiv 3\mod 11.$$