$\,a^{(p-1)(q-1)}\equiv 1\pmod{\!pq}$ for primes $p\neq q$ not dividing $a$ I am to show that from $a \equiv 16^{12 \cdot18}(\bmod 247)$, we have

*

*$a \equiv 8^{12 \cdot 18}(\bmod 247)$

*$a \equiv 1(\bmod 247)$
How do I proceed here? I tried at first using Fermat's little theorem, but I noticed that $247$ is not a prime, which is required. I'm therefore somewhat lost, and I would appreciate some help, tips, or something that can enlighten me.
We have not learned, and are not supposed to learn Euler's theorem in the course this exercise is taken from. I note that 247 is a Carmichael number, but we haven't really learned how to solve for those either. Are there any other ways to solve this?

Hint: $ $ since Euler's phi theorem is unknown,  prove a $2$-prime case as below using little Fermat. Then the OP follows as special case $\,p,q = 13,\,19,\,$ $\ N\! =\! (p\!-\!1)(q\!-\!1)\!=\! 12\cdot 18,\ $ $\,a = 16,\,8$.
Lemma $\,\ \color{#c00}{p,q\nmid a},\,\ \color{#0a0}{p\!-\!1,q\!-\!1\mid N}\,\Rightarrow\, a^N\equiv 1\pmod{\!pq},\,$ for $\,\color{#90f}{{\rm primes}\ \,p\neq q}$
Proof $\,\bmod p\!:\ a^N = (\color{#c00}{a^{\large p-1}})^{\large \color{#0a0}{N/(p-1)}}\!\equiv \color{#c00}1^{\large \color{#0a0}K}\!\equiv 1\,$ by little $\rm\color{#c00}{Fermat}.\,$ Similarly $\,a^N\equiv 1\pmod{\!q},\,$ $\rm\color{#90f}{hence}$ $\,a^{N}\equiv 1\pmod{\!pq}\,$ by LCM or CCRT = Constant-case CRT.
Remark $\, $ Above we used basic congruence arithmetic rules, notably $\,b\equiv c\Rightarrow\, b^k\equiv c^k,\,$ the Congruence Power Rule.
Since the proof works for any expt $\color{#0a0}N$ that is a  $\rm\color{#0a0}{common\ multiple\ of}$ $\color{#0a0}{\,p\!-\!1,\,q\!-\!1}\,$ it also works for $N = $ LCM = least common multiple $= [p\!-\!1,q\!-\!1] = [12,18] = 6[2,3] = 36\,$ or any multiple.
When you learn Euler's totient (phi) theorem you may note that as above we can also use LCM to reduce the exponents, a generalization known Carmichael's Lambda Theorem.
