Prove that 8 is the remainder of $5^{336}$ by $23$

Question

I've searched this website and while there are a few questions similar to mine, I couldn't find what I was looking for/a specific method for what I want to do.

I want to understand how one would prove that the remainder of $5^{336}$ by $23$ is $8$, or in other words, $$5^{336}\equiv 8 \pmod{23}.$$

Can anyone help me understand how one would approach a problem like this?

Answer 1

$23$ is prime, so $\phi(23) = 22$. You can thus always take the exponent modulo $22$ (by Euler's theorem, or in this special case Fermat's little theorem). $$5^{336} \equiv 5^6 \equiv 2^3 = 8 \pmod{23}$$ The last congruence is because $5^2 = 25 \equiv 2$

Remark on Brute-Forcing
We actually have $\mathrm{ord}_{23}(5) = 22$ so you'd have to do many computations until you arrive there. This is highly impractical.

Remark on modulus in exponents
We know that $$a^{\mathrm{ord}_n(a)}\equiv 1 \pmod n$$ by definition of the order of an element. Also we know that the order of an element is a divisor of the group order, alas $\mathrm{ord}_n(a) | \phi(n)$. This allows us to make two statements: $$a^k \equiv a^{k\bmod \mathrm{ord}_n(a)} \pmod n$$ and as a corollary of that, $a^k \equiv a^{k\bmod \phi(n)} \pmod n$.

Answer 2

Hint $\ {\rm mod}\ 23\!:\ \underbrace{\color{#c00}{5^{\large 22}}\equiv\color{#c00}1}_{\rm little\ Fermat}\Rightarrow\, 5^{\large 336}\equiv 5^{\large 6+\color{#c00}{22}(15)}\equiv \color{#0a0}{5}^{\large \color{#0a0}{2}\cdot 3}\,\color{#c00}{(5^{\large 22})}^{\large 15}\equiv \color{#0a0}2^{\large 3} \color{#c00}{(1)}^{\large 15}\equiv 8 $

where we have used the fundamental Congruence Product and Power Rules.

Remark $ $ Generally, if $\,a^e\equiv 1\pmod m\,$ then exponents on $\,a\,$ can be considered mod $\,e,\,$ i.e. $\ a^{\large j}\equiv a^{\large k}\pmod m\,\ $ if $\,\ j\equiv k\pmod e.\ $ This may be proved exactly as above, i.e.

$$ \begin{array}{}\color{#c00}{a^{\large e}\equiv 1}\\ j = k\! +\! en\end{array}\Rightarrow\,\ a^{\large j}\equiv a^{\large k+en}\equiv a^{\large k}\color{#c00}{(a^{\large e})}^{\large n}\equiv a^{\large k}\color{#c00}{(1)}^{\large n}\equiv a^k\!\!\pmod m\qquad $$