Finding solutions for $x^3\equiv 1 \bmod n$

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

Does it help if n is prime?

• 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$. – Daniel Fischer Nov 2 '13 at 22:49
• wolframalpha.com/input/?i=x^3+%3D+1+mod+211 – Jorge Fernández Hidalgo Nov 2 '13 at 22:57
• Isn't this a counterexample? – Jorge Fernández Hidalgo Nov 2 '13 at 22:58
• No, $211 \equiv 1 \pmod{3}$. – Daniel Fischer Nov 2 '13 at 22:59
• Oh, oops, sorry I got confused with the answer below, you are saying something different. – 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.
• 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. – Gerry Myerson Nov 2 '13 at 23:16
• 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$. – Daniel Fischer Nov 3 '13 at 0:23