Modular Arithmetic with large exponents! Decide whether each of the following is true or false without using a calculator:
The problem is:
$$11^{99}\equiv 1\pmod{5}$$
Now I know I can break the $11$ into $(10+1)^{99}$ and maybe rewrite it as $(10+1)^{98}\times (10+1)$
and then realize that $10+1\equiv 1\pmod{5}$ and then just deal with $(10+1)^{98}$ but that means I have to do this $97$ times until at the end I have $10+1\equiv 1\pmod 5$ but I feel like this is a very stupid way to look at it. Is there a little trick of sorts that I can use on problems like this when the exponents are huge?
 A: Notice below $$11^{99} - 1^{99} = (11-1)(11^{98}+11^{97}+\cdots+1) =10M$$
Since $11\equiv 1\pmod{5}$, we have $11^k\equiv 1^k \pmod{5}$  
In general : 
$$a\equiv b\pmod{n} \implies a^k\equiv b^k \pmod{n}$$
A: Hint: Euler's Theorem. For the case of modulo prime, use the corollary of it, Fermat's Little Theorem
A: There are many ways to approach this.
One way is to note that for all $n$: if $\gcd(a,n) = 1$:
$a^{\phi(n)} = 1$ (mod $n$). This is known as Euler's Theorem.
Here, we have $a = 11, n = 5$, and $\phi(5) = 4$, so we have:
$11^{99} = (11^{96})(11^3) = (11^{4})^{24}(11^3) = (1^{24})(11^3) = 11^3$ (mod $5$).
Then it is easy to see:
$11^3 = (5\cdot 20 + 1)(5 \cdot 2 + 1) = 5\cdot (200 + 22) + 1$ so that:
$11^3 = 1$ (mod $5$).
It is also easy to prove by induction on $k$, that $11 = 1$ (mod $5$) $\implies 11^k = 1$ (mod $5$).
Certainly this is self-evident for $k = 1$, since $11 = 2\cdot 5 + 1$.
Suppose now that $11^{k-1} = 1$ (mod $5$). This means there is some integer $t$, so that:
$11^{k-1} = 5t + 1$.
Then $11^k = (11^{k-1})(11) = (5t + 1)(10 + 1) = 5\cdot(10t + t + 2) + 1$, so taking:
$t' = 10t + t + 2$, we see $11^k = 5t' + 1$, that is: $11^k = 1$ (mod $5$).
Now this holds for ANY natural number $k$, so in particular, $k = 99$.
