# there are at least $\frac{p+1}{2}$ integers $d$, with $0 \leq d < p$, so that the equation $x^3+x=d \pmod p$ has a root$\pmod p$

Prove that for infinitely many prime numbers p, there are at least $$\frac{p+1}{2}$$ integers $$d$$ with $$0 \leq d such that the equation $$x^3+x \equiv d \pmod p$$ has a root $$\pmod p$$

My first attempt was to prove by contradiction that the equation $$x^3+x=d \pmod p$$ does not have three different roots for some $$p$$, but I realized that I was wrong. How can I prove or disprove the question ?

(Sorry for my English)

• what book are you using? Nov 25, 2018 at 2:36
• @WillJagy This is actually a problem from a paper that my friend gave me. I have tried to answer it for many days, but every conjecture of mine is incorrect or hard to prove/disprove.
– rice
Nov 25, 2018 at 2:37
• What do you mean by "the statement"? You have a "Let..." and a "Suppose...", but neither of these is a statement. Do you mean this? "Prove that for infinitely many prime numbers $p$, there are at least $\frac{p+1}{2}$ integers $d$ with $0\le d<p$ such that the equation $x^3+x\equiv d$ (mod $p$) has a root (mod $p$)." Nov 25, 2018 at 2:55
• @TonyK Yes, thank you. Should I edit the question?
– rice
Nov 25, 2018 at 3:01
• @rice: Yes, I think so. Nov 25, 2018 at 3:18

This follows from the following result together with the infinitude of primes $$p\equiv-1\pmod6$$.

Result. If $$p\equiv-1\pmod3$$ then the polynomial $$f(x)=x^3+x$$ takes exactly $$(2p-1)/3$$ distinct values as $$x$$ ranges over the field $$\Bbb{F}_p$$.

I will assume that $$p\equiv-1\pmod3$$ in everything that follows.

Being cubic, the polynomial $$f(x)$$ can take any value in $$\Bbb{F}_p$$ at most three times. Let $$N_i=|\{d\in\Bbb{F}_p\mid\text{the equation x^3+x=d has exactly i solutions x\in\Bbb{F}_p}\}|$$ for all $$i=0,1,2,3$$, be the number of elements $$d\in\Bbb{F}_p$$ that appear in the set of values of $$f(x)$$ exactly $$i$$ times.

Fact 1. $$N_1+2N_2+3N_3=p.$$

Proof. This is because, counted with multiplicity, $$f(x)$$ takes exactly $$p$$ values, one for each choice of $$x$$, and we have $$N_i$$ values appearing exactly $$i$$ times. QED.

Fact 2. $$N_2=0$$.

Proof. Assume contrariwise that for some $$d\in\Bbb{F}_p$$ the polynomial $$f_d(x):=x^3+x+d$$ has exactly two zeros in $$\Bbb{F}_p$$. By the Vieta relations the sum of all the zeros of this cubic is equal to zero. This means that the third zero is the negative of the sum of the two other zeros, obviously also an element of $$\Bbb{F}_p$$. For $$f_d$$ to have only two zeros in $$\Bbb{F}_p$$ it is therefore necessary that one of those three zeros is a double zero. But, a doubled zero is a common zero of $$f_d(x)$$ and its derivative $$f_d'(x)=3x^2+1$$. If $$f_d'(x)=0$$ it follows that $$-3=9x^2=(3x)^2$$ is a square in $$\Bbb{F}_p$$. If this happens, the element $$\omega=(-1+\sqrt{-3})/2$$ exists in $$\Bbb{F}_p$$. Because $$\omega$$ is a primitive third root of unity, we see, by Lagrange's theorem from elementary group theory, that $$3\mid|\Bbb{F}_p^*|=p-1$$ contradicting the assumption $$p\equiv-1\pmod3$$. QED.

Let us next consider the set $$S=\{(x,y)\in\Bbb{F}_p^2\mid x^3+x=y^3+y\}.$$

Fact 3. The set $$S$$ has exactly $$2p+1$$ elements.

Proof. Obviously all the $$p$$ pairs $$(x,x), x\in\Bbb{F}_p$$ are in the set $$S$$. We have the factorization $$(x^3+x)-(y^3+y)=(x^3-y^3)+(x-y)=(x-y)(x^2+xy+y^2+1).$$ So for a pair $$(x,y), x\neq y$$, to be in the set $$S$$ it must satisfy the equation $$x^2+xy+y^2+1=0. \qquad(*)$$ Reusing the argument from my answer to the linked question we see that $$(*)$$ has exactly $$p+1$$ solutions $$(x,y)$$, and for all of them $$x\neq y$$. QED.

Proof (of the main result). We can count the cardinality of the set $$S$$ also as follows. If $$d$$ appears as a value of $$f(x)$$ twice, say $$d=f(x)=f(y)$$, then the pairs $$(x,y)$$ and $$(y,x)$$ both appear in $$S$$. If $$d$$ appears as a value thrice, say $$d=f(x)=f(y)=f(z)$$, then all the six pairs $$(x,y)$$, $$(y,x)$$, $$(x,z)$$, $$(z,x)$$, $$(y,z)$$ and $$(z,y)$$ of distinct elements appear in the set. Therefore $$|S|=p+2N_2+6N_3.$$ Taking Facts 2 and 3 into account we arrive at the equation $$2p+1=|S|=p+6N_3$$ implying that $$N_3=\frac{p+1}6.$$ Plugging everything into Fact 1 we can then solve that $$N_1=p-3N_3=p-3\cdot\frac{p+1}6=\frac{p-1}2.$$ The number of values taken by $$f(x)$$ is thus $$N_1+N_2+N_3=\frac{p-1}2+\frac{p+1}6=\frac{2p-1}3$$ proving the main result.

• It looks like we could make some progress when counting the number of values of $f(x)$ also in the case $p\equiv1\pmod3$ using tese methods. But, this answer is long enough as it is. Nov 25, 2018 at 12:55
• In case of curiosity about the particular primes for which $x^3 + x + c$ factors completely, see zakuski.utsa.edu/~jagy/Hudson_Williams_1991.pdf and the more general zakuski.utsa.edu/~jagy/Spearman_Williams_1992.pdf My recollection is that there is a single linear factor when $(\Delta |p) = -1,$ then irreducible for primes represented by forms outside the subgroup $J$ in discriminant of positive binary quadratic forms $\Delta = -(4 + 27 c^2)$ Nov 25, 2018 at 16:46