Solving Congruences with Polynomials: A Prime Challenge

[Fantini]

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. (Nod) Thanks.

 

[Sudharaka]

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. (Nod) 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]

Thank you Sudharaka, but now I have found the solution. :) I will post it later.

Cheers.

 

[Sudharaka]

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\]

Interested to see your solution. :)

 

[Opalg]

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. :D

Thanks for the search link, Opalg!