0
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

See @Servaes for a very nice answer.

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you know that there is a $g$ such that $g^{36}\equiv-1\pmod{73}$? $\endgroup$ – user80979 Apr 1 '14 at 22:54
  • $\begingroup$ any idea why that is the case? Is it from a theorem? $\endgroup$ – user80979 Apr 1 '14 at 23:11
  • $\begingroup$ Yes, look up something like "primitive roots modulo prime". If you have not yet studied this topic you would be better to go with @Servaes' answer. $\endgroup$ – David Apr 1 '14 at 23:13
  • $\begingroup$ I did learn this same topic hence I'm even more confused as to how that conclusion was derived. Any help will be greatly appreciated! $\endgroup$ – user80979 Apr 1 '14 at 23:24
  • $\begingroup$ $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. $\endgroup$ – David Apr 1 '14 at 23:31

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.