Find all solutions to $x^{10} = 1 \pmod {377}$

Question

Find all solutions to $x^{10} \equiv 1 \pmod {377}$

I noticed that $x^{10} \equiv 1 \pmod {377}$ can be written as:
$(x^5+1)(x^5-1)\equiv 0 \pmod {377}$
also $377 = 13 \times 29$

Any help would be greatly appreciated

Answer 1

Hint: by the Chinese remainder theorem, we can find all solutions to this equation by first finding all solutions to $$ x^{10} \equiv 1 \pmod{13}\\ x^{10} \equiv 1 \pmod{29} $$

To find the solutions mod $13$, it is slightly useful to note that $x^{10} = x^{12 - 2} = x^{-2}$.

---

Full solution: The first equation has solution $$ x^{10} \equiv 1 \pmod{13} \iff \\ x^{-2} \equiv 1 \pmod{13} \iff \\ x^{2} \equiv 1 \pmod{13} \iff \\ x \equiv \pm 1 \pmod{13} $$ so, we have two solutions to the first equation. For the second, the same trick looks a little weirder: $$ x^{10} \equiv 1 \pmod{29} \implies\\ (x^{10})^3 \equiv 1 \pmod{29} \implies\\ x^{30 - 28} \equiv 1 \pmod{29} \implies\\ x^2 \equiv 1 \pmod{29} $$ so, in order for $x$ to be a solution to the original equation, we must also have $x^2 \equiv 1 \pmod{29}$. So, our full solution is $$ x \equiv \pm 1 \pmod{29} $$ and you may verify that both of these satisfy the original equation.

Now, applying the CRT (calculating $[13^{-1}]_{29} = 9$ and $[29^{-1}]_{13} = 9$), we end up with $4$ solutions to the original equation (mod 377). In particular, we have $$ x \equiv 1 \pmod {377}\\ x \equiv -1 \pmod {377}\\ x \equiv 13[13^{-1}]_{29}(-1) + 29[29^{-1}]_{13}(1) \equiv 144 \pmod {377}\\ x \equiv 13[13^{-1}]_{29}(1) + 29[29^{-1}]_{13}(-1) \equiv -144 \pmod {377}\\ $$