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.
Notice that $$2^4=16\equiv16-17\equiv -1\pmod{17}$$ Also notice that $$2^8=2^4\cdot 2^4\equiv (-1)\cdot (-1)\equiv 1\pmod{17}$$ Then $$2^{2143}=(2^8)^{267}\cdot 2^7\equiv 1^{267}\cdot 2^7\equiv 2^7=128\equiv9\pmod{17}$$
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)$.
Without getting into equivalence classes, multiplication mod $n$ is associative. That means that if you know $i$ such that $a^i \mod n=1$ then $a^k \mod n = (a^i \mod n)^{\mathrm{quot}(k,i)} a^{k \mod i} \mod n=a^{k \mod i} \mod n$, where quot represents the quotient in integer division. For a prime modulus, multiplication mod $n$ also has an inverse, so that such a (nonzero) $i$ will always exist and in fact will be in $\{ 1,2,\dots,n-1 \}$. In fact little Fermat's theorem tells us that if $n$ is prime and the base isn't divisible by $n$ then $i=n-1$. So you could have figured out that $i=16$ in your case without brute force.
(Side note: not sure how better to format this, since I don't really want to use the $\equiv$ notation in this case.)
