How can I find all the numbers mod n such that $x^3\equiv 1 \bmod n$?

Does it help if n is prime?

  • 3
    $\begingroup$ It helps if $n$ is prime. If $n$ is prime and $n \not\equiv 1 \pmod{3}$, then there is only one solution to $x^3 \equiv 1 \pmod{n}$, and that's $1$. If $n$ is a prime $\equiv 1 \pmod{3}$, there are three solutions. You can for example find them by computing $a^{(n-1)/3}\pmod{n}$ until you find the first value $y \neq 1$, then the three solutions are $1,y,y^2$. $\endgroup$ – Daniel Fischer Nov 2 '13 at 22:49
  • $\begingroup$ wolframalpha.com/input/?i=x^3+%3D+1+mod+211 $\endgroup$ – Jorge Fernández Hidalgo Nov 2 '13 at 22:57
  • $\begingroup$ Isn't this a counterexample? $\endgroup$ – Jorge Fernández Hidalgo Nov 2 '13 at 22:58
  • $\begingroup$ No, $211 \equiv 1 \pmod{3}$. $\endgroup$ – Daniel Fischer Nov 2 '13 at 22:59
  • $\begingroup$ Oh, oops, sorry I got confused with the answer below, you are saying something different. $\endgroup$ – Jorge Fernández Hidalgo Nov 2 '13 at 23:00

If $n$ is a power of a prime, $n=p^r$, $r\gt1$, then, if you can solve $x^3\equiv1\pmod p$, you can lift $x$ to a solution modulo $n$ by Hensel's Lemma, q.v.

If you can factor $n$ as a product of powers of distinct primes, then you can solve the problem modulo each of these prime powers, and sew them together using the Chinese Remainder Theorem, q.v.

If $n$ is not prime, and you can't factor it, life is more difficult.

  • $\begingroup$ Can we know that there are no more than 3 solutions? $\endgroup$ – Jorge Fernández Hidalgo Nov 2 '13 at 23:12
  • 1
    $\begingroup$ No. If $n$ is divisible by 2 or more $3k+1$ primes, there will be more than 3 solutions. E.g., if $n=91=7\times13$. Think about that Chinese Remainder Theorem. $\endgroup$ – Gerry Myerson Nov 2 '13 at 23:16
  • 1
    $\begingroup$ Also, @Omnitic, if $n$ is divisible by $9$ (or a higher power of $3$, but then it is divisible by $9$), you get three solutions from that, so $63 = 3^2\cdot 7$ gives you $3\cdot 3 = 9$ solutions, $1, 4, 16, 22, 25, 37, 43, 46, 58$. $\endgroup$ – Daniel Fischer Nov 3 '13 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.