Modular Exponentiation using Euler's Theorem

Question

How would one go about computing the following value:

$8^{223}$ mod 69

using Euler's Theorem:

$a^{\phi(m)} \equiv 1 (\text{mod }m)$

I've found the factorization of 69 to be 23 and 3 and used this to find the phi function:

$\phi(69) = (23^{1} - 23^{0})(3^{1} - 3^{0}) = 44$

Using this, I can conclude the following:

$8^{44} \text{mod } 69 = 1$

But, I'm not sure where to go from here. Any help would be appreciated.

Answer 1

Euler's theorem states that if $a$ and $m$ are co-prime; then $$a^{\varphi(m)}\equiv 1\bmod m.$$

Since $8$ and $69$ are indeed co-prime; we have $\varphi(69)=\varphi(3)\varphi(23)=44,$ so $$8^{44}\equiv 1\mod 69.$$

Working in modulo $69$, we have $$8^{220}=(8^{44})^5=1,$$ and so $$8^{223}=8^{220}\cdot8^3=8^3=29. $$