# 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.

• Might be useful to recognize that $6=-1 \mod 7$ Commented Nov 28, 2016 at 0:26
• @KitterCatter Can you explain it a bit more? (possibly as an answer). Is it derived from $n | (a-b)$? Commented Nov 28, 2016 at 0:29
• I don't know about using fermat (not a mathematician by trade) but it might be helpful to know that the Euler totient function of a prime,$p$ is $p-1$ and that if $a^{\phi(p)} \equiv 1 \mod p$ Commented Nov 28, 2016 at 0:31
• Be sure to understand the relation between "mod" as a binary operator vs. ternary relation. See this answer and this one for more on this. If you only know the operator form you will be severely encumbered. Commented Nov 28, 2016 at 0:32
• See also  How do I compute $a^b\,\bmod c$ by hand? for many approaches. Commented Sep 8, 2020 at 15:55

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 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 mod Distributive law, e.g. here & 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.) Or we can compute the power mod (coprime) factors of the modulus and then combine them by CRT, e.g. see 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.

In any case, we can always exponentiate by repeated squaring, which is quite efficient.

• Often it proves simpler to first reduce $\,e\,$ using Euler's Criterion or quadratic reciprocity, e.g. see here.. Commented Jun 8, 2019 at 13:31

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.

• Thanks for the answer. But can you please explain how you arrived to step 3? (in your four-step part of the answer), and why you have calculated the gcd(7, 13)? Commented Nov 28, 2016 at 0:58
• Sure. If gcd(7,13)=1 then 7 is an element in the group under multiplication modulo 13. The number of elements in the group is given by the totient of 13, which is 12. Therefore 7^12 = 1 modulo 13. this strips the problem down to figuring out modulo 12. 100 is 4 modulo 12 so we only need to look at 7^4 modulo 13 Commented Dec 10, 2019 at 15:14