# How do you Compute $7^{1000} \mod 24$?

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?

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

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.

Note that $49\equiv 1 \mod 24$

• So $7^{N}$ 24 modulos (is it a verb?) to N/2 which solves pretty fast. That was the thought, right? – JTP - Apologise to Monica Mar 7 '14 at 18:24
• 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$ – Mark Bennet Mar 7 '14 at 18:27

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

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

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

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}{\left\langle #1 \right\rangle} \newcommand{\braces}{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\equalby}{{#1 \atop {= \atop \vphantom{\huge A}}}} \newcommand{\expo}{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}{\,\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}{\left\vert #1\right\rangle} \newcommand{\ol}{\overline{#1}} \newcommand{\pars}{\left( #1 \right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[]{\,\sqrt[#1]{\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}{\underline{#1}} \newcommand{\verts}{\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}$$