1
$\begingroup$

I'm trying to learn more about modular arithmetic by practicing some problems, but I'm having some difficulty with this one.

For which primes p will there be a solution to x^3 + 1 ≡ (mod p) other than x ≡ - 1 (mod p)?

I'm given a hint that there must be primitive roots mod p, and if a is a primitive root mod p we know the smallest positive integer k for which a^k ≡ -1 (mod p). But I'm not sure how that helps me find a solution other than x = -1 (mod p).

Could anyone help me with this problem?

Thanks!

$\endgroup$
2
$\begingroup$

$\newcommand{\Z}{\mathbb{Z}}$Let $F = \Z / p \Z$, with $p$ a prime. Consider the polynomial $$ g = x^{6} - 1 = (x^{3} - 1) (x^{3} + 1) = (x^{3} - 1) (x + 1) (x^{2} - x + 1) \in F[x]. $$ You want to know when $$f = x^{2} - x + 1$$ has a root in $F$ different from $-1$.

Clearly you must have $p \ne 2$ then, otherwise the only possible root of $f$ in $F$ is $1 = -1$, and $f(1) = 1^{2} - 1 + 1 = 1 \ne 0$.

Also, you want $p \ne 3$, as noted in another answer, because if $p = 3$ the polynomial $x^{2} - x + 1 = x^{2} + 2 x + 1 = (x + 1)^{2}$ has only $-1$ as a root.

So we have $p > 3$.

Now a root $\alpha$ of $f$ is a root of $g$, and thus $\alpha^{6} = 1$. So $\alpha$ has multiplicative order a divisor of $6$, thus one of $1, 2, 3, 6$.

As $f(1) = 1 \ne 0$, we have $\alpha \ne 1$.

As $\alpha \ne -1$, we have $\alpha^{2} \ne 1$.

Also, since $0 = f(\alpha) = \alpha^{2} - \alpha + 1$, we have $\alpha^{2} = \alpha - 1$. It follows that $\alpha^{3} = \alpha \alpha^{2} = \alpha (\alpha - 1) = \alpha^{2} - \alpha = -1 \ne 1$, so $\alpha^{3} \ne 1$.

We have shown that $\alpha$ does not have order $1, 2, 3$. Thus $\alpha$ has order $6$.

So a necessary condition is for the multiplicative group $F^{*}$ to have an element of order $6$, that is $6 \mid p - 1$, or $$p \equiv 1 \pmod{6}.$$ Since $F^{*}$ is cyclic, this is also a sufficient condition.

$\endgroup$
0
$\begingroup$

Hint: Try with $p = 7$ and $p = 5$ (both happen to have $3$ as primitive root, which you should check to be sure), find the order of the primitive root in each case. Use that order to see what powers of $3$ solves the equation.

Looking at your results after trying the above, what exactly is it with $p = 7$ that allows multiple solutions, while $p = 5$ fails to have them? Now generalize.

$\endgroup$
  • $\begingroup$ I managed to confirm that 5 and 7 both have 3 as a primitive root, with order for p = 5 as 4 and the order for p = 7 as 6. From here, I tried to find the values of 3^order mod 5 and mod 7, but I seem to get different answers in both cases. Could you please guide me a bit further on this problem? Thanks! $\endgroup$ – Kami May 7 at 8:45
  • $\begingroup$ @Kami For $p = 7$, with the order of the primitive root being $6$, what are the possible orders of powers of the primitive root? And what about for $p = 5$? And if we want additional solutions to $x^3-1\equiv 0$, what orders should we look for? $\endgroup$ – Arthur May 7 at 8:51
  • $\begingroup$ For p = 7, I get 1 and 2 as the orders of the powers of the primitive root. For 4 as the order when p = 5, I also get values as 1, 2. So for x^3 - 1, we would have to look for orders ≠ 1,2? I don't know much about this topic so I'm quite confused. Sorry for the trouble! $\endgroup$ – Kami May 7 at 9:07
  • $\begingroup$ @Kami For $p=7$, what is the order of $3^2$? And in both cases, your list is missing the order of $3$ itself. $\endgroup$ – Arthur May 7 at 9:12
0
$\begingroup$

Another hint:

Factor the equation $$ x^3+1=(x+1)(x^2-x+1)=0 $$

The quadratic factor must have two roots distinct from $-1$, which implies $p>3$. The discriminant $-3$ has to be a non-zero square. Use the law of quadratic reciprocity.

$\endgroup$
  • $\begingroup$ I'm not familiar with the law of quadratic reciprocity, could you please elaborate on how to continue solving this problem? Thanks! $\endgroup$ – Kami May 7 at 8:43
  • $\begingroup$ Do you know the Legendre symbol? $\endgroup$ – Bernard May 7 at 8:51
0
$\begingroup$

Another approach. Suppose that $p$ has the form $6k+5$, with $k$ an integer. Then, by Fermat's little theorem, for $c$ any non-zero residue modulo $p$, \begin{align*} c&=c^{6k+5}\\ \implies c^2&=c^{12k+10}\\ \implies c&=c^{12k+9}=(c^{4k+3})^3, \end{align*} so $c$ is a cube. In addition, $0^3=0$. Thus, by the pigeonhole principle, the cubes of all residues are distinct, so no residue $x$ except $-1$ can have $x^3=-1\mod p$.

$\endgroup$
0
$\begingroup$

Since $\,a\,$ is a primitive root there are $\,j,k\,$ with $\, x \equiv a^{\large j}\,$ and $\, {-}1 \equiv a^{\large k}\,$ hence $$x^{\large 3}\equiv -1\iff a^{\large 3j}\equiv a^{\large k}\iff 3j\equiv k\!\!\!\pmod{\!p-1}$$

This has a unique solution $\,j\equiv 3^{-1}k\pmod{p-1}$ $\iff 3\nmid p-1$ so there's a solution besides $\,x\equiv -1\iff p\equiv 1\pmod{\!3}\iff p\equiv 1,4\pmod{\!6}.\,$ But $\,p\neq 4+6n\,$ by $\,p\,$ odd.

$\endgroup$

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.