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?
 A: 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.
A: Note that $49\equiv 1 \mod 24$
A: You can choose the method you like best:


*

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

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

*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$.
A: Hint: $7\equiv1\mod3$, and $7\equiv-1\mod8$, and $24=3\cdot8$.
A: $\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}
$$

