Verifying a solution of modular arithmetic question.

Question

I was given the following practice question with the solution:

A practice question: find $\phi(27)$ and use it to calculate $300^{93} \pmod {27}$.

Solution: Since $\phi(27) = 18$, then: $$(300^{93\pmod {18}}\pmod{27})\pmod{27}=(3^{93\pmod{18}})\pmod{27}=3^3\pmod{27} =0.$$

My question is: Based on what theorem we mod the exponent $93\pmod{18}$ and why?

Answer 1

You don't need all this stuff to compute $300^{93}\mod 27$: since $3^3=\equiv 0\mod 27$, we have $$300^{93}=3^3 3^{90}100^{93}=0\cdot3^{90}100^{93}\equiv 0\mod 27.$$

Answer 2

Apply the Lemma below, where all congruences are $\!\pmod m\,$ unless otherwise notated, and where we have employed standard congruence arithmetic rules.

Lemma $\ $ If $\,\ \color{#c00}{a^N\equiv 1}\,\ $ then $\ J\equiv K\pmod N\ \Rightarrow\ a^J\equiv a^K$

Proof $\ \ J = K + IN\,\Rightarrow\, a^J \equiv a^{K+IN}\equiv a^K (\color{#c00}{a^N})^I\equiv a^K \color{#c00}1^I\equiv a^K$