Mod of numbers with large exponents [modular order reduction]

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

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 Lemma 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 we apply the below fact.

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 conversely if $\,a\,$ has order $\,\color{#c00}e\,$ mod $\,m$

Proof $\ $ Wlog $\,n\ge k\,$ so $\,a^{\large n-k} a^{\large k}\equiv a^{\large k}\!\iff a^{\large n-k}\equiv 1\iff n\equiv k\pmod{\!e}\,$ by here, where we 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).

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.