# Polynomials

#### Fantini

MHB Math Helper
I'm having trouble with the following question:

Construct a polynomial $q(x) \neq 0$ with integer coefficients which has no rational roots but is such that for any prime $p$ we can solve the congruence $q(x) \equiv 0 \mod p$ in the integers.

Any hints on how to even start the problem will be strongly appreciated. Thanks.

#### Sudharaka

##### Well-known member
MHB Math Helper
I'm having trouble with the following question:

Construct a polynomial $q(x) \neq 0$ with integer coefficients which has no rational roots but is such that for any prime $p$ we can solve the congruence $q(x) \equiv 0 \mod p$ in the integers.

Any hints on how to even start the problem will be strongly appreciated. Thanks.
Hi Fantini,

Let me give you a hint. Consider the Fermat's little theorem and see whether you can think of a polynomial satisfying the given conditions.

Kind Regards,
Sudharaka.

#### Fantini

MHB Math Helper
Thank you Sudharaka, but now I have found the solution. I will post it later.

Cheers.

#### Sudharaka

##### Well-known member
MHB Math Helper
Thank you Sudharaka, but now I have found the solution. I will post it later.

Cheers.
You are welcome. I was thinking about the polynomial $$q(x)=x^p-x$$ so that the congruence $$q(x)\equiv 0(\mbox{mod } p)$$ could be solved in the integers (by the Fermat's little theorem), but alas $$q$$ has rational roots (examples are $$x=0,1$$). So to make it rational root less, we can do a little improvement. Take,

$q(x)=x^p-x+p$

By the Rational root theorem the list of possible rational roots that this polynomial could have are $$\pm 1,\pm p$$. Clearly, $$x= \pm 1, p$$ do not satisfy the equation $$q(x)=0$$. Let $$x=-p$$ be a root of $$q(x)$$. Then,

$q(-p)=0\Rightarrow (-p)^p+2p=0$

If $$p$$ is even, $$p=2$$ and we have $$p^p+2p=8=0$$ which is contradictory. If $$p$$ is odd,

$\Rightarrow -p^p+2p=0\Rightarrow p^{p-1}=2$

Since $$p$$ is an odd prime, $$p\geq 3$$. Hence the equation $$p^{p-1}=2$$ cannot be satisfied. Therefore we see that there are no rational roots for,

$q(x)=x^p-x+p$

#### Opalg

##### MHB Oldtimer
Staff member
A quick internet search comes up with the polynomial $p(x) = (x^2-2)(x^2-3)(x^2-6)$ (see here, for example).

The reason that works is that if 2 and 3 are both quadratic non-residues mod $p$ then their product 6 will be a quadratic residue. On the other hand, $p(x)$ clearly has no rational roots.

#### Fantini

The solution is similar to what Opalg's search found. We considered the polynomial $q(x) = (x^2 +1)(x^2 +2)(x^2 -2)$ and, using elementary number theory arguments such as Legendre's symbol and quadratic residues, proved it satisfied the conditions of the statement.