# Mod of numbers with large exponents

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 this formula:

$$a \equiv b\pmod n \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 kth 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$ – Kitter Catter Nov 28 '16 at 0:26
• @KitterCatter Can you explain it a bit more? (possibly as an answer). Is it derived from $n | (a-b)$? – Roshnal Nov 28 '16 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$ – Kitter Catter Nov 28 '16 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. – Bill Dubuque Nov 28 '16 at 0:32

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

• Very nice answer! When you reference Lil' Fermat did you mean $a\not\equiv0\mod13$? also it looks like you missed a bracket for the exponent in $a^{12} \equiv 1 \mod 13$ – Kitter Catter Nov 28 '16 at 0:47
• Thanks for the answer! I'm still a little unclear on how you got to $10^2$ from $7^4$? – Roshnal Nov 28 '16 at 1:03
• $7^4=(7^2)^2=49^2\equiv 10^2$, that's all. – Bernard Nov 28 '16 at 1:12
• Ah okay, thanks! It's clear now :) – Roshnal Nov 28 '16 at 1:15
• @Kitter Catter: Oh! Yes. I should have re-read my answer before posting. I even missed a pair of brackets. It's fixed now. Thanks for pointing the typos! – Bernard Nov 28 '16 at 1:15

Hint $$\,$$ The key idea is to use modular order reduction on exponents as in the Lemma below. We can find small exponents $$\,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.$$

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}.\$$ Further,  conversely

$$\qquad n\equiv k\pmod{\! \color{#c00}e}\,\Longleftarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}\ \,$$ 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 you are familiar with modular inverses 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}$$.

• Often it proves simpler to first reduce $\,e\,$ using Euler's Criterion or quadratic reciprocity, e.g. see here.. – Bill Dubuque Jun 8 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)? – Roshnal Nov 28 '16 at 0:58