With the help of Chinese remainder theorem show that $ x^{144} \equiv 1 \pmod{ 323}$

Question

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?

Answer 1

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

Answer 2

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?

Answer 3

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.

Answer 4

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