0
$\begingroup$

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.

$\endgroup$
2
  • 6
    $\begingroup$ What is $2^{\varphi(437)}$? $\endgroup$
    – Daniel Fischer
    Oct 11, 2020 at 14:36
  • 2
    $\begingroup$ Oh thanks... Can't understand why I did not come up with that's simply idea! Thank you Daniel. $\endgroup$
    – Senna
    Oct 11, 2020 at 14:40

3 Answers 3

Reset to default
0
$\begingroup$

Hint:

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .