3
$\begingroup$

I'm being asked to compute $7^{1000} \mod 24$. I have Fermat's Little Theorem and Euler's Theorem. How do I use these to compute $7^{1000} \mod 24$? I'm stuck because $24$ is not prime. In this case, I think I have to use Euler's Theorem. Can anyone show me what to do?

$\endgroup$
  • 3
    $\begingroup$ Did you notice that if you square 7 you get 1 mod 24? That may help here I'd think. $\endgroup$ – JB King Mar 7 '14 at 18:02
5
$\begingroup$

You could simply take the square of $7$ to find that $$7^2 \equiv 1 \mod 24$$

But just for educational purposes: By Euler's Theorem (valid because $GCD(7, 24) = 1$),

$$7^{\phi{(24)}} \equiv 1 \mod 24$$

Now, $\phi(24) = 24\cdot\left(1 - \frac{1}{2}\right)\cdot\left(1-\frac{1}{3}\right) = 8$. (See here for details). Hence,

$$7^8 \equiv 1 \mod 24$$

Raise both sides to the power of $125$ to deduce that :

$$7^{1000} \equiv 1 \mod 24$$

If go ahead and use the Charmichael function, you will obtain an even stronger result than Euler's Theorem:

$$7^2 \equiv 1 \mod 24$$

which is what we saw earlier on.

$\endgroup$
3
$\begingroup$

Note that $49\equiv 1 \mod 24$

$\endgroup$
  • $\begingroup$ So $7^{N}$ 24 modulos (is it a verb?) to N/2 which solves pretty fast. That was the thought, right? $\endgroup$ – JTP - Apologise to Monica Mar 7 '14 at 18:24
  • $\begingroup$ The point is that $7^{1000}=(7^2)^{500}$ - also for modulus $m$ we have $(km+r)(lm+s)=(kl+k+l)m+rs \equiv rs \mod m$ $\endgroup$ – Mark Bennet Mar 7 '14 at 18:27
2
$\begingroup$

You can choose the method you like best:

  1. Simply calculate powers of $7$ modulo $24$... In this case $$7^{1000}\equiv (7^2)^{500}\equiv 49^{500}\equiv 1^{500}\equiv 1 \bmod 24.$$

  2. Since $\gcd(7,24)=1$, you can use Euler's theorem. Note that $\varphi(24)=8$. $$7^{1000}\equiv (7^8)^{125}\equiv 1^{125}\equiv 1 \bmod 24.$$

  3. You can use the Chinese remainder theorem. Since $24=3\cdot 8$, we have that $x\equiv 7^{1000}$ modulo $3$ and $8$, if and only if $x\equiv 7^{1000} \bmod 24$. Now, $$7^{1000}\equiv 1^{1000}\equiv 1 \bmod 3, \text{ and } 7^{1000}\equiv (-1)^{1000}\equiv 1 \bmod 8,$$ and therefore $7^{1000}\equiv 1 \bmod 24$.

$\endgroup$
1
$\begingroup$

Hint: $7\equiv1\mod3$, and $7\equiv-1\mod8$, and $24=3\cdot8$.

$\endgroup$
  • $\begingroup$ How do I use $24 = 3 \cdot 8$? Is there a fact about modular arithmetic that I'm unaware of here? $\endgroup$ – Newb Mar 7 '14 at 18:03
  • $\begingroup$ The Chinese remainder theorem! $\endgroup$ – Álvaro Lozano-Robledo Mar 7 '14 at 18:07
  • 1
    $\begingroup$ @Newb: What number in between $0$ and $23$ gives the remainder $1$ when divided through both $3$ and $8$ ? :-) $\endgroup$ – Lucian Mar 7 '14 at 18:09
0
$\begingroup$

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\exists\ p,\mu\ \in\ {\mathbb N}}$ such that $\ds{7^{n} = 24p + \mu}$ where $\ds{0 \leq \mu < 24}$.

Also $$ 7^{n + 2} = \pars{24p + \mu}7^{2} = 24p\times 49 + 48\mu + \mu = \pars{49p + 2\mu}\times 24 + \mu\,,\ \left\vert% \begin{array}{rcl} \mbox{Also,}&& \\ n = 0 & \imp & \mu = 1 \\ n = 1 & \imp & \mu = 7 \end{array}\right. $$

Then, $$ 7^{n} \mod 24 =\left\lbrace \begin{array}{rcl} 1 & \mbox{if} & n\ \mbox{is}\ even \\ 7 & \mbox{if} & n\ \mbox{is}\ odd \end{array}\right. $$

Then $$ \color{#00f}{\large 7^{1000}\mod 24 = 1} $$

$\endgroup$

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.