Mod of numbers with large exponents [modular order reduction] I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two:

*

*$13^{100} \bmod 7$

*$7^{100} \bmod 13$
I've also heard of the Congruence Power Rule
$$a \equiv b \,\Rightarrow\, a^k \equiv b^k \pmod n $$
But I don't see how exactly to use that here, because from $13^1 \bmod 7\,$ I get $6$, and $13^2 \bmod 7$ is $1$. I'm unclear as to which one to raise to the $k$'th power here (I'm assuming $k = 100$?)
Any hints or pointers in the right direction would be great.
 A: The formula you've heard of results from the fact that congruences are compatible with addition and multiplication.
The first power  $13^{100}$ is easy: $13\equiv -1\mod 7$, so 
$$13^{100}\equiv (-1)^{100}=1\pmod 7.$$
The second power uses Lil' Fermat: for any number $a\not\equiv 0\mod 13$, we have $a^{12}\equiv 1\pmod{13}$, hence 
$$7^{100}\equiv 7^{100\bmod12}\equiv 7^4\equiv 10^2\equiv 9\pmod{13}$$
A: Hint $\, $ The key idea is that any periodicity of the exponential map $\,n\mapsto a^n\,$ allows us to use modular order reduction on exponents as in the results below. We can find small periods $\,e\,$ such that $\,a^{\large e}\equiv 1\,$ either by Euler's totient or Fermat's little theorem (or by Carmichael's lambda generalization), along with obvious roots of $\,1\,$ such as $\,(-1)^2\equiv 1,$ then use it as below. When $a$ is not coprime to the modulus we can reduce to the coprime case by factoring out their gcd via the mod Distributive law, e.g. here, and many more here (or we can generalize the results below to exponents not in the initial preperiodic part of the rho $(\rho)$ shaped orbit.)
Theorem $ \ \ $ Suppose that: $\,\ \color{#c00}{a^{\large e}\equiv\, 1}\,\pmod{\! m}\ $ and $\, e>0,\ n,k\ge 0\,$ are integers. Then
$\qquad n\equiv k\pmod{\! \color{#c00}e}\,\Longrightarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}\,\ $ [and $\rm\color{#f60}{conversely}$ if $\,a\,$ has order $\,\color{#c00}e\,$ mod $\,m$]
Proof $\ $ Wlog $\,n\ge k\,$ so $\,a^{\large n-k}\color{#0a0}{a^{\large k}}\equiv \color{#0a0}{a^{\large k}}\!\!\!\overset{\color{#0a0}{\rm cancel}\!\!}\iff a^{\large n-k}\equiv 1$ $\Leftarrow\!\![\color{#f50}\Rightarrow]\ n\equiv k\pmod{\!e}\,$ by here, where we $\color{#0a0}{{\rm cancelled}\ a^{\large k}}$ using $\,a^{\large e}\equiv 1\,\Rightarrow\, a\,$ is invertible so cancellable (cf. below Remark).
Corollary $\ \ \bbox[7px,border:1px solid #c00]{\!\bmod m\!:\,\  \color{#c00}{a^{\large e}\equiv 1}\,\Rightarrow\, a^{\large n}\equiv a^{\large n\bmod \color{#c00}e}}\,\ $ by $\ n\equiv n\bmod e\,\pmod{\!e}$
Remark $ $ If modular inverses are known then it is not necessary to restrict to nonnegative powers of $\,a\,$ above since $\,a^{\large e}\equiv 1,\ e> 0\,\Rightarrow\,$ $a$ is invertible by $\,a a^{\large e-1}\equiv 1\,$ so $\,a^{\large -1}\equiv a^{\large e-1}.\,$ As motivation it may help to consider the additive analog of  above multiplicative form, namely
Theorem $ \ \ $ Suppose that: $\,\ \color{#c00}{e\cdot a \equiv\, 0}\,\pmod{\! m}\ $ and $\, e>0,\ n,k\,$ are integers. Then
$\ \quad n\equiv k\pmod{\! \color{#c00}e}\,\Longrightarrow\,n\cdot a \equiv k\cdot a\pmod{\!m},\, $ and conversely if $\,a\,$ has (+)order $\,\color{#c00}e\,$ mod $\,m$
Corollary $\ \ \bbox[7px,border:1px solid #c00]{\!\bmod m\!:\,\  \color{#c00}{e\cdot a\equiv 0}\,\Rightarrow\, n\cdot a\equiv (n\bmod \color{#c00}e)\cdot a}\,\ $ by $\ n\equiv n\bmod e\,\pmod{\!e}$
For example: $\bmod 10\!:\,\ 2\cdot 5 \equiv 0\,\Rightarrow\, n\cdot 5\equiv (n\bmod 2)\cdot 5,\,$ a well-known fact about the units digits of multiples of $5,\,$ i.e. it is $\,0\,$ if $\,n\,$ is even, else $\,5.$
For example: $\bmod 12\!:\,\ 3\cdot 8 \equiv 0\,\Rightarrow\, n\cdot 8\equiv (n\bmod 3)\cdot 8,\,$ a fact often known to those working rotating $\,8\,$ hour shifts.
The analogy will be clarified if one studies group theory (these are basic facts on cyclic groups).
Remark $ $ When $\,n < e\,$ then $\,n\bmod e = n\,$ so mod order reduction yields no simplification. Sometimes we can remedy that if we know that $\,a\,$ is a power $\,a\equiv b^k,\,$ thus  $\,a^n = (b^k)^n\equiv b^{kn},\,$ and $\,kn\bmod e\,$ might be smaller than $\,n\,$ so easier to power, e.g. let's consider an example when $\,k = 3,\,$ i.e. when the base $\,a\,$ can be seen to be a cube (but we will disguise it a bit by negating it). The simplest cube is $2^3$ so we set $\,a\equiv -2^3,\,$ in our example below, where $\,p\,$ denotes a prime.
$$\begin {align}\bmod p = 163\!:\, \ \ \ \ \ \ \ \ 155^{54}\equiv\: &(-2^3)^{54}\!\equiv 2^{162}\!\equiv2^{p-1}\equiv 1,\ \ \text{by Fermat;  generally}\\[.2em]
\bmod p=6j\!+\!1\!:\ (p\!-\!8)^{2j}\equiv\: &(-2^3)^{2j}\!\equiv\, 2^{6j}\,\equiv 2^{p-1}\equiv 1
\end{align}\ \ \ $$
The analog of the above for $\,k=2\,$ is essentially the easy part of Euler's Criterion, e.g. here.
A: Quick answer:
$13 = 2\cdot 7-1$ so $13\equiv-1\mod 7$ and therefore $13^{100} \equiv (-1)^{100} \mod 7$
Other one is fairly quick:
\begin{eqnarray}
\phi(13) = 12\\ 
\gcd(7,13)=1\\
7^{100}\equiv7^{4} \mod13\\
7\rightarrow10\rightarrow5\rightarrow9
\end{eqnarray}
Probably a nicer way to do that.
