2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: Look at $5^1, 5^2, 5^3,\ldots$ modulo $23$, and look for a pattern. $\endgroup$ – vadim123 Feb 2 '15 at 20:42
  • $\begingroup$ @vadim123 I started out doing so, but I was looking for a more abrangent method. I know that works, but brute-forcing has it's limitations (when no computer/calculator is around) and it takes too long for numbers with longer patterns. $\endgroup$ – HolyThunder Feb 2 '15 at 20:47
  • 1
    $\begingroup$ @HolyThunder Do you have little fermat / euler at your disposal? $\endgroup$ – AlexR Feb 2 '15 at 20:47
  • $\begingroup$ @AlexR now I do. This is a question I came across while studying for an exam but unfortunately I missed about half the semester's classes due to being in the hospital and I missed a lot of important material including the aforementioned Fermat's Little theorem and Euler's. $\endgroup$ – HolyThunder Feb 2 '15 at 20:54
  • $\begingroup$ This question might be interesting for you. (And maybe also some other questions in the frequent tab of the tag modular arithmetic.) $\endgroup$ – Martin Sleziak Feb 3 '15 at 14:59
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can I always take the exponent modulo $\phi(mod)$? Thanks a lot man, I knew there was a way to solve these without bruteforcing them. $\endgroup$ – HolyThunder Feb 2 '15 at 20:52
  • 1
    $\begingroup$ @HolyThunder Yes, as you see in the article about Euler's theorem $$a^{\phi(n)} \equiv 1 \pmod{n} \qquad\forall a$$ Computing $\phi(n)$ is easy if you know the prime factorisation of $n$. $\endgroup$ – AlexR Feb 2 '15 at 20:53
  • 1
    $\begingroup$ Calculating $5^{336}$ directly is not quite impractical: ten multiplications, by my count, as $((((((5^2)^25)^2)^25)^2)^2)^2)^2$, all done modulo $23$. $\endgroup$ – Lubin Feb 2 '15 at 21:00
  • $\begingroup$ @Lubin Square-and-multiply reduces the overhead, but that's still bad when doing by hand as opposed to $1$ modulo and $1$ multiplication (don't forget all the moduli in SQM). $\endgroup$ – AlexR Feb 2 '15 at 21:02
  • $\begingroup$ Absolutely: your suggestion is the only wise route to the answer. Actually, writing down all powers of $5$ modulo $23$ is not out of the question at all, especially since $5^2=2$. Once you see that $5^{22}=1$, you’re almost home free. $\endgroup$ – Lubin Feb 2 '15 at 21:02
2
$\begingroup$

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

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