How do you evaluate high powers in modulo expressions? How would you evaluate $ 2^{2143} \pmod{17}?$
For instance, I was looking through my notes and the example I have is :
 $5^{131} \pmod{14}$
We look at the powers $ 5^i$  modulo $14$ and notice that they repeat at $i = 6$
Now since $131 = 5 \pmod{6}$ then $5^{131} = 5^5 = 3 \pmod{14}$
The answer is $3$. However, I do not understand this logic at all. 

Fermat's Little Theorem:
If $p$ is a prime and $gcd(a,p) = 1$, then $a^{p-1} \equiv 1 (mod \; p)$.
Generalization of Fermat's Little Theorem (Euler's Theorem):
Let $a,n \in \mathbb{N}$ and $gcd(a,n) = 1$, then $a^{\phi(n)} \equiv 1 (mod \; n)$, where $\phi(n)$ = number of positive integers less than $n$ and coprime to $n$.
In the first example, 17 is a prime and $gcd(2, 17) = 1$. Hence $2^{16} \equiv 1 (mod \; 17)$. Hence $2^{2143} = 2^{16 \times 133 + 15} = (2^{16})^{133} \cdot 2^{15} \equiv 1^{133} \cdot 2^{15} \equiv 2^{15} (mod \; 17)$. Also note that $2^4 \equiv -1 (mod \; 17) \implies 2^{15} = (2^4)^3 \cdot 2^3 \equiv (-1)^3 \cdot 8 \equiv -8 \equiv 9 (mod \; 17)$.
In the second example, we have to use the generalization because 14 is not a prime and $gcd(5,14) = 1$. Also, $\phi(14) = \phi(2 \times 7) = \phi(2) \times \phi(7) = 1 \times 6 = 6$. (This comes from the fact that $\phi$ is a multiplicative function. A number theoretic function $f$ is multiplicative if $f(mn) = f(m) \cdot f(n)$ whenever $gcd(m,n) = 1$).
Hence $5^6 \equiv 1 (mod \; 14)$. Also, $131 = 6 \times 21 + 5$. Thus, $5^{131} = (5^6)^{21} \cdot 5^5 \equiv 1^{21} \cdot 5^5 \equiv 5^5 (mod \; 14)$.
If you want more transparency in the logic, write $131 = 6q + r$ where $q$ is the quotient and $r$ is the remainder when 131 is divided by 6. Repeat the calculation above using $q$ and $r$ to note that the value of $q$ has no effect on the answer. All that matters is the value of $r$ which is nothing but $131 (mod \; 6)$.
