$437$ divides $16^{99} -1$. Help to finish it.

Question

I am doing an exercise and find a question which I can't answer. The exercise asks to show that $16^{99}\equiv 1 \pmod{437}$. Since $\gcd(16,437)=1$, Euler's theorem says

$$ 16^{\varphi (437)}\equiv 1\pmod{437} \Rightarrow $$$$16^{396}\equiv 1\pmod{437} \Rightarrow $$

$$(16^{99})^4\equiv 1\pmod{437}$$

How can I assert from this that $16^{99}\equiv 1\pmod{437}? $

Any help is welcome. Thanks in advance.

Answer 1

Hint:

$16^{99}=2^{4\cdot99}$ and $\varphi(437)=\dotsm$

Answer 2

Because $437=23\cdot19$ and $$4^{11}=2^{22}\equiv1(\operatorname{mod}23)$$ and $$4^9=2^{18}\equiv1(\operatorname{mod}19)$$

Answer 3

You have\begin{align}(-3)^3\equiv-8\pmod{19}&\implies(-3)^9\equiv1\pmod{19}\\&\implies16^9\equiv1\pmod{19}\\&\implies16^{99}\equiv1\pmod{19}.\end{align}On the other hand\begin{align}(-7)^2\equiv3\pmod{23}&\implies(-7)^4\equiv9\pmod{23}\\&\implies(-7)^8\equiv12\pmod{23}\\&\implies(-7)^{11}\equiv12\times(-7)\times3=1\pmod{23}\\&\implies16^{11}\equiv1\pmod{23}\\&\implies16^{99}\equiv1\pmod{23}.\end{align}Since $437=19\times23$, it follows from this that $16^{99}\equiv1\pmod{437}$.