$\begingroup$With the help of Chinese remainder theorem show that $ x^{144} \equiv 1 \pmod{323}$ for all $x$ relatively prime to 323.
The problem with me is that I used to use CRT when $x$ is raised to a power of 1, but how can I work with $x$ to the power of 144, could anyone explain this for me please?
$\endgroup$44 Answers
$\begingroup$We have $323=324-1=18^2-1=17\times 19$. So by CRT, it suffices to show $x^{144}\equiv 1\pmod{17}$ and $x^{144}\equiv 1\pmod{19}$ for all $x$ coprime to 17 and 19. Can you finish it from here?
$\endgroup$1$\begingroup$Hints:
By Fermat’s little theorem, since $17$ and $19$ are prime, $x^{16}\equiv1\mod17$ and $x^{18}\equiv1\mod19.$
Use the constant case of the Chinese remainder theorem.
$\endgroup$0$\begingroup$As $323=17\cdot 19$, so $x$ is coprime both to $17$ and $19$. By lil' Fermat, $x$ has order $16$ modulo $17$, and $18$ modulo $19$.
Therefore, it has order $\operatorname{lcm}(16,18)=144$ modulo $323$.
$\endgroup$1$\begingroup$$323=17 \cdot 19$, and by Fermat's Little Theorem: $x^{144}=(x^{18})^8 \equiv 1 \pmod{19}$ $x^{144}=(x^{16})^9 \equiv 1 \pmod{17}$ For all $x$ coprime to $323$. Can you finish from here? It's a straightforward application of CRT.
$\endgroup$
