# 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?

• Hint: $11\equiv 1\pmod{5}$. – vadim123 Mar 25 '15 at 17:44
• After eight questions asked I think it is time to learn how to properly write mathematics in this site: meta.math.stackexchange.com/questions/5020/… – Timbuc Mar 25 '15 at 17:44
• @vadim123 I think your hint is the best answer. – David K Mar 25 '15 at 18:04

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

Hint: Euler's Theorem. For the case of modulo prime, use the corollary of it, Fermat's Little Theorem

• Not necessary. $11$ raised to the power of itself any number of times ends with $1$, take away, $1$ from it, it ends with $0$, so it's divisible by $5$ – GohP.iHan Apr 21 '15 at 4:32
• @GohP.iHan, the OP further asked if there's any method in general that'll allow him to approach problems like this. That's precisely the reason I mentioned these theorems in my answer. – Prasun Biswas Apr 21 '15 at 5:33

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