Congruence modulo high power problem

Question

The question is simple: Find 2^(2014)(mod 11). I literally only found out about congruence modulo yesterday and I cannot think for the life of me how to go about solving this problem. I can obviously see I need to simplyfy it, but I'm not what use that would be to me.

Answer 1

Let $\mathcal{U}_{11}$ be the set of integers coprime to $11$. Then, since $11$ is prime we have $$\mathcal{U}_{11}=\{1,2,3,4,5,6,7,8,9,10\}.$$

Let's write the first few powers of $2$ mod $11$, I'll represent the operation of multiplying by $2$ by arrows. Starting from $2^0$ we have

$$1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 5 \rightarrow 10 \rightarrow 9 \rightarrow 7 \rightarrow 3 \rightarrow 6...$$ before repeating since we've seen every element in $\mathcal{U}_{11}$.

So, we see that after every multiple of ten entries in the sequence, we get back to $1$, that is $2^{10m}=1$. Let $m=201$, then $2^{2010}=1$. From here, we observe we just have another $4$ entries to go until we get to the $2014^{th}$ power. Just count $4$ along the sequence to give us $$2^{2014}=5.$$

Answer 2

Fermat's Little Theorem states that

If $n \in \mathbb N$, $p$ is a prime, and $p \not | \space \space n$ then $n^{p-1} \equiv1\pmod p$

If $n \in \mathbb N$, $p$ is a prime, then $n^p \equiv n \pmod p$

We have:

\begin{align} 2^{2014} = 2^{11\cdot183 + 1} \end{align}

Then, by the definition,

\begin{align} 2^{2014} & = 2^{11\cdot 183+1} \\ 2^{11\cdot 183+1} &\equiv 2^{183+1} \pmod {11}\\ \end{align}

\begin{align} 2^{183+1} &= 2^{184} \\ 2^{184} & = 2^{11\cdot {16} + 8} \\ 2^{11\cdot {16} + 8} &\equiv 2^{16+8} \pmod {11}\\ \end{align}

\begin{align} 2^{16+8} &= 2^{24} \\ 2^{24} & = 2^{11\cdot {2} + 2} \\ 2^{11\cdot {2} + 2} &\equiv 2^{2+2} \pmod {11}\\ \end{align}

We can easily see that $2^4 = 16$. Thus $2^{2014} \equiv 5 \pmod{11}$.

Alternatively, using the second part of the theorem,

We have:

\begin{align} 2^{2014}=2^{10\cdot 201 + 4} & \equiv 2^{4} \pmod {11} \\ \implies 2^{2014} \equiv 16 &\equiv 5 \pmod {11} \\ \end{align}

Notice that $2^{10\cdot 201}$ is equivalent to $0 \pmod {11}$. Thus, we can just eliminate it. I believe these two methods of solving the problem are equally correct. Hopefully you can see what I have manipulated to get an answer.