$\,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?
 A: 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.
A: You have $247 = 13 \cdot 19.$  If you prove that $13 \mid 16^{12\cdot 18} - 8^{12\cdot 18}$, and $19 \mid 16^{12\cdot 18} - 8^{12\cdot 18}$, that will prove part a.  You can use Fermat's Little Theorem for this.
After you work out the details, I don't think you'll have any trouble with part b.
A: First of all, $247$ is not a Carmichael number.
Second of all, use Fermat's little theorem with the prime factors of $247=13\times19$:
$16^{12}\equiv1\bmod13$, so $16^{12\cdot18}\equiv1\bmod13$, and $16^{18}\equiv1\bmod19$, so $16^{12\cdot18}\equiv1\bmod19$.
Then, as Bill Dubuque suggests, apply the constant case of the Chinese remainder theorem
to conclude that $16^{12\cdot18}\equiv1\bmod247$.
