4
$\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$
  • 1
    $\begingroup$ Might be useful to recognize that $6=-1 \mod 7$ $\endgroup$ – Kitter Catter Nov 28 '16 at 0:26
  • $\begingroup$ @KitterCatter Can you explain it a bit more? (possibly as an answer). Is it derived from $n | (a-b)$? $\endgroup$ – Roshnal Nov 28 '16 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$ – Kitter Catter Nov 28 '16 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$ – Bill Dubuque Nov 28 '16 at 0:32
5
$\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 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}$$

$\endgroup$
  • $\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$ – Kitter Catter Nov 28 '16 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 '16 at 1:03
  • $\begingroup$ $7^4=(7^2)^2=49^2\equiv 10^2$, that's all. $\endgroup$ – Bernard Nov 28 '16 at 1:12
  • $\begingroup$ Ah okay, thanks! It's clear now :) $\endgroup$ – Roshnal Nov 28 '16 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 '16 at 1:15
2
$\begingroup$

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

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

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.