Mod of numbers with large exponents [modular order reduction]

Solution 1:

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

Solution 2:

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.

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.