8
$\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 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.

$\endgroup$
5
  • 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

8
$\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
8
$\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 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.

$\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
1
$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.