10
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Might be useful to recognize that $6=-1 \mod 7$ $\endgroup$ Nov 28, 2016 at 0:26
  • 1
    $\begingroup$ @KitterCatter Can you explain it a bit more? (possibly as an answer). Is it derived from $n | (a-b)$? $\endgroup$
    – Roshnal
    Nov 28, 2016 at 0:29
  • $\begingroup$ 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$ $\endgroup$ Nov 28, 2016 at 0:31
  • $\begingroup$ 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. $\endgroup$ Nov 28, 2016 at 0:32
  • 2
    $\begingroup$ See also $ $ How do I compute $a^b\,\bmod c$ by hand? for many approaches. $\endgroup$ Sep 8, 2020 at 15:55

3 Answers 3

15
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ 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$ $\endgroup$ Nov 28, 2016 at 0:47
  • $\begingroup$ Thanks for the answer! I'm still a little unclear on how you got to $10^2$ from $7^4$? $\endgroup$
    – Roshnal
    Nov 28, 2016 at 1:03
  • $\begingroup$ $7^4=(7^2)^2=49^2\equiv 10^2$, that's all. $\endgroup$
    – Bernard
    Nov 28, 2016 at 1:12
  • $\begingroup$ Ah okay, thanks! It's clear now :) $\endgroup$
    – Roshnal
    Nov 28, 2016 at 1:15
  • $\begingroup$ @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! $\endgroup$
    – Bernard
    Nov 28, 2016 at 1:15
12
$\begingroup$

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.

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

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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)? $\endgroup$
    – Roshnal
    Nov 28, 2016 at 0:58
  • 1
    $\begingroup$ 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 $\endgroup$ Dec 10, 2019 at 15:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .