# Does there exist a cubic polynomial $f(x)$ such that $f(x)\equiv0 \pmod p$ has no integer solutions if $p\equiv 3\pmod 4$?

As we know that $f(x)=x^2+1\equiv0 \pmod p$ has no integer solutions if $p\equiv 3\pmod 4$, does there exist a cubic polynomial $f(x)=ax^3+bx^2+cx+d~(a,b,c,d \in\mathbb Z,a\neq 0)$ such that $f(x)\equiv0 \pmod p$ has no integer solutions if $p\equiv 3\pmod 4$?

I only know that $f(x)=0$ has no integer solutions.

If $p\equiv 1\pmod{3}$ and $a\in\mathbb{F}_p^*$ is not a cubic residue $\!\!\pmod{p}$, i.e.: $$a^{\frac{p-1}{3}}\not\equiv 1\pmod{p},$$ there are no integer solutions to $$x^3 - a\equiv{0}\pmod{p}.$$ Just take $a\in\{2,3,4,5\}$ for $p=7$ or $a\in\{2,3,4,5,6,9,10,13,14,15,16,17\}$ for $p=19$.

In general, $f(x)$ has no roots in $\mathbb{F}_p$ iff it is irreducible over $\mathbb{F}_p$ - this depends only on the discriminant to be a quadratic residue or not and another function of the coefficients to be a cubic residue or not (we can drop the last condition if $p\equiv 2\pmod{3}$, since in such a case every element of the field is a cubic residue).

If you were looking for a "universal polynomial" $f(x)$ such that for every $p\equiv 3\pmod{4}$ $$f(x)\equiv 0\pmod{p}$$ has no solutions in $\mathbb{F}_p$, no such polynomial exists, since for the quadratic reciprocity law and the Dirichlet theorem the discriminant of $f(x)$ is a non-quadratic residue for some prime $q\equiv 3\pmod{4}$, hence $f(x)$ splits over $\mathbb{F}_q$ in virtue of the Stickelberger's criterion. Since $f(x)$ is a third-degree polynomial, this implies that $f(x)$ has a root in $\mathbb{F}_q$, contradiction.

• I just showed that $x^3-2\equiv 0\pmod{7}$ and $x^3-2\equiv 0\pmod{19}$ have no integer solutions, so the answer is affirmative. – Jack D'Aurizio Aug 1 '14 at 12:51
• Ah, I see. But IMHO the question asks about a cubic polynomial that (like $x^2+1$) doesn't have zeroes mod all primes of the form $4k+3$. – Grigory M Aug 1 '14 at 12:52
• Oh, I just interpreted the question in a different way. Ok, I will update my answer. – Jack D'Aurizio Aug 1 '14 at 12:55
• It is the general condition for a third degree polynomial to be irreducible over a finite field: the discriminant must be a quadratic residue and another quantity must be a non-cubic residue. If for some third degree polynomial over $\mathbb{F}_p$ the discriminant is a quadratic residue, the polynomial splits. – Jack D'Aurizio Aug 1 '14 at 13:09
• I didn't get why the discriminant is necessarily a non-QR modulo some $p$. For example, what if the discriminant is a square? (in $\Bbb{Z}$) – Jyrki Lahtonen Aug 2 '14 at 22:32

You want the polynomial to have no root modulo (at least) half of the primes.

If $G$ is the galois group of $f$ (a subgroup of $S_3$), the polynomial has a linear factor modulo $p$ iff the reciprocity symbol at $p$ is an element of the Galois group with a fixpoint. By Cebotarev's density theorem, you need $G' = \{g \in G \mid g$has a fixpoint$\}$ to be less than half the size of $G$.

You can quickly enumerate the subgroups of $S_3$ and find that only a cyclic group of order $3$ can work.

Since such an extension is abelian, the primes where $f$ factors are those who land modulo $m$ into the kernel of a character $\chi : (\Bbb Z/m\Bbb Z)^* \to C_3$ for some $m$.

Since $(\Bbb Z / 2^k \Bbb Z)^*$ has no $3$-part, it is useless to have powers of $2$ in $m$ : if $\chi$ is such a character it can be defined modulo some odd $m$ (in fact the only things that may appear in $m$ are $3^2$ and $p^1$ for $p \equiv 1 \pmod 3$)

Then by Dirichlet's theorem there must be primes landing in $\ker \chi$ that are congruent to $3 \pmod 4$

• No, the question doesn't require the polynomial to have a root mod all p=4k+1 — and since 1/3<1/2 I don't see an immediate contradiction with Chebotarev's theorem. – Grigory M Aug 1 '14 at 13:09
• If I understood it right, mercio's argument seems to work. The case when the Galois group is $S_3$ can be ruled out, because for two thirds of primes inertia degrees $f=1$ or $f=2$ occur in the splitting field, and these force a linear factor modulo the said prime. The case $G=C_3$ (by virtue of being abelian) brings in the characters, and only leaves the possibility that the set of split primes consists of those falling to one third of residue classes modulo an integer that must have a prime factor $>2$? – Jyrki Lahtonen Aug 3 '14 at 7:54

Here is an analogous fact. If $$p\equiv 1\mod 3$$ where $p\neq m^2+27n^2$ for any integers $m$ and $n$, then $$x^3-2\equiv0\mod p$$ has no integer solutions by the cubic reciprocity law for $\left[\frac{2}{p}\right]_3$.

• @GrigoryM Sorry, I misremembered how cubic reciprocity goes. I'll tone it down. – alex.jordan Aug 1 '14 at 9:39
• @gammatester p=3 is not 1 mod 3 – Grigory M Aug 1 '14 at 12:45