2

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

TenaliRaman
  • 3,846
mike russel
  • 311

1 Answers1

4

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

Ben Grossmann
  • 225,327
  • I'm kind of still stuck. $x^{10} = 1 + 13k \equiv 1 \pmod {29}$. This implies that $k \equiv 0 \pmod {29}$ so $x = 1$ I figured the answer would be something other than $1$ – mike russel Mar 04 '15 at 04:12
  • While I'm solving the first congruence, I let $ x = 1, 2, ..., 12$ and got that $1^{10} \equiv 12^{10} \equiv 1 \pmod {13}$ I plugged in $12$ for $x$ in the second congruence and didn't get $1$ does that mean $1$ is the only solution? – mike russel Mar 04 '15 at 04:31
  • Hint++: $x^{-2} \equiv 1$, $x^2x^{-2} \equiv x^2$ – Dane Bouchie Mar 04 '15 at 04:34
  • 1
    Also think about the other solutions to $k$, not just $k=0$, so if $k \equiv 0 \mod 29$ what other solutions are there for $k$ as well? (Or just use the Chinese Remainder Theorem for this case, as what you would be doing is just a proof of the CRT for this case) – Dane Bouchie Mar 04 '15 at 04:37