# How many solutions are there to $x^3\equiv-1\pmod{365}$?

How many solutions are there to $$x^3\equiv-1\pmod{365}$$?

I found that there is only one solution mod $$5$$, but mod $$73$$ I'm a little confused. Factoring out $$x^3 + 1=(x+1)(x^2-x+1)$$, the second equation has no real solutions, hence $$x\equiv-1\pmod{73}$$ is the only solution mod $$73$$. So by the Chinese remainder theorem, there is only $$1*1=1$$ solution. Is this correct?

• What was $9^3$? – Daniel Fischer Apr 1 '14 at 22:40

Note that $x^3+1$ factors as $x^3+1=(x+1)(x^2-x+1)$, where $x^2-x+1$ is irreducible in $\Bbb{F}_5[x]$. So indeed there is only one solution $\mod5$. But in $\Bbb{F}_{73}[x]$ we have $$x^3+1=(x+1)(x+8)(x-9),$$ so there are three solutions $\mod{73}$, which are $-1$, $-8$ and $9$. By the Chinese remainder theorem we then have $1\times3=3$ solutions.
For something a bit more systematic, $73$ is prime and so there is a primitive root $g$ modulo $73$. Every element of $\Bbb Z_{73}$ except for $0$ (which is not a solution) can be written as $x=g^k$ for some $k=0,1,2,\ldots,71$. Since $-1\equiv g^{36}$ we have \eqalign{x^3\equiv-1\pmod{73}\quad &\Leftrightarrow\quad g^{3k}\equiv g^{36}\pmod{73}\cr &\Leftrightarrow\quad 3k\equiv36\pmod{72}\ ;\cr} since $\gcd(3,72)=3$ and this is a factor of $36$, there are three solutions.
• How do you know that there is a $g$ such that $g^{36}\equiv-1\pmod{73}$? – user80979 Apr 1 '14 at 22:54
• $g^{72}\equiv1$, definition of primitive root. Taking square roots (ok modulo a prime), $g^{36}\equiv\pm1$. But $g^{36}\equiv1$ would contradict the definition of a primitive root. – David Apr 1 '14 at 23:31