Polynomials Consisting of Quadratic Factors with Roots Modulo Any Positive Integer

Abstract

We give an infinite family of polynomials that have roots modulo every positive integer but fail to have rational roots. Each polynomial in this family is made up of monic quadratic factors that do not have linear terms. The proofs in this note are accessible to anyone with a basic knowledge of undergraduate elementary number theory.

MSC:

• Primary 11C08
• Secondary 11A99

1 Introduction

We concern ourselves with polynomials f with integer coefficients such that $f(x)\equiv 0(\text{mod}m)$ is solvable for every positive integer m. If a polynomial f has an integer root, then f clearly has roots modulo every positive integer. However, there exist polynomials that have roots modulo every positive integer but do not have any rational root. Such polynomials provide counterexamples to the local-global principle in number theory (see [3, pp. 99–108] for more details on the local-global principle).

Given a cube-free integer $n\ne 1$, Hyde, Lee, and Spearman proved in [4] that$$g(x)=(x^3-n)(x^2+3)$$has no rational roots but has roots modulo every positive integer if and only if $n\equiv 1(\text{mod}9)$ and all prime factors of n are congruent to 1 modulo 3.

It is well known that if p, q are distinct odd primes such that $p\equiv q\equiv 1$ (mod 4) and p is a square modulo q, then the polynomial$$h(x)=(x^2-p)(x^2-q)(x^2-pq)$$has no rational roots but has roots modulo every positive integer (see [6, pp. 139–140]). Let c and d be square-free integers not equal to 1, let $c_1=\frac{c}{\text{gcd}(c,d)}$ and $d_1=\frac{d}{\text{gcd}(c,d)}$. Hyde and Spearman obtained necessary and sufficient conditions for the polynomial$$p(x)=(x^2-c)(x^2-d)(x^2-c_1{d}_1)$$ to have a root modulo every integer but have no rational root [5]. We obtain necessary and sufficient conditions for polynomials, made up of any number of similar quadratic factors, to have roots modulo every integer but have no rational root.

Note that the congruence $f(x)\equiv 0(\text{mod}m)$ is solvable for every positive integer m if and only if the congruence $f(x)\equiv 0(\text{mod}{p}^b)$ is solvable for each prime number p and each positive integer b. This is a consequence of the Chinese remainder theorem.

Given a prime p and an integer n, we denote the Legendre symbol of n with respect to p by $\left(\frac{n}{p}\right)$. When $p\nmid n,\left(\frac{n}{p}\right)=+1$ if n is a square modulo p and $\left(\frac{n}{p}\right)=-1$ otherwise. When $p|n,(\frac{n}{p})=0$. Given a prime p and a nonzero integer l, $p^a\left|\right|l$ will denote that $p^a(a\ge 1)$ is the highest power of p dividing l. Our main result is the following theorem.

Theorem 1.

Let $a_1,a_2,\dots ,a_n$ be n ($\ge 3$) distinct nonzero square-free integers, none of which is 1. Then the polynomial $f(x)=(x^2-a_1)(x^2-a_2)\cdots (x^2-a_n)$ has roots modulo every positive integer if and only if the following conditions are satisfied:

1. There exists $T\subseteq \{1,2,\dots ,n\}$ of odd cardinality such that:

   1. the product $\prod _{j\in T}{a}_j$ is a perfect square;

   2. for every $j\in T$ and for every odd prime p dividing a_j, there exists $i\in \{1,\dots ,n\},i\ne j$, such that $\left(\frac{a_i}{p}\right)=+1$.

2. One of the a_i is of the form $8m+1$ for some $m\in \mathbb{Z}$ and $m\ne 0$.

We note that the polynomial $f(x)={\prod }_{i=1}^n(x^2-a_i)$ in Theorem 1 cannot have a rational root, since none of the a_i is a perfect square.

2 Results on Quadratic Residues

In this section, we collect some results on quadratic residues that will be used to prove Theorem 1.

Proposition 1.

Let p be an odd prime, $e\ge 1$, and $a\in \mathbb{Z}$ such that $p\nmid a$. Then a is a square modulo p^e if and only if $\left(\frac{a}{p}\right)=+1.$

Since $p\nmid a$, the proof of this statement is an immediate consequence of Hensel’s lemma applied to the polynomial $q(x)=x^2-a$. (See [6, p. 135] for a proof.)

The next proposition characterizes square-free integers, not equal to 1, that are square modulo every power of 2.

Proposition 2.

1. Let $a\in \mathbb{Z}$ be an odd number. Then a is a square modulo $2^i$ for every $i\ge 1$ if and only if $a=8m+1$ for some $m\in \mathbb{Z}$. (See [6, p. 136].)

2. Let a be a square-free integer not equal to 1. Then a is a square modulo $2^i$ for every $i\ge 1$ if and only $a=8m+1$ for some $m\in \mathbb{Z}$ and $m\ne 0$. (See [5, Lemma 2.5].)

Proof.

If a is odd, then the result follows from 2(a). On the other hand, if a is even, then $a\equiv 2(\text{mod}\mathrm{}4)$ because it is square-free. Since 2 is not a square modulo 2², a cannot be a square modulo 2². $■$

3 Some Useful Lemmas

We will also use the following lemma proved by Fried (see [1] and [2]).

Lemma 1.

Let $a_1,a_2,\dots ,a_n$ be finitely many nonzero integers. Then the following conditions are equivalent:

1. For each prime p that does not divide ${\prod }_{i=1}^n{a}_i$, at least one of the a_i is a square modulo p.

2. There exists $T\subseteq \{1,2,\dots ,n\}$ of odd cardinality such that $\prod _{j\in T}{a}_j$ is a perfect square.

Lemma 2.

Let p be an odd prime and $a\in \mathbb{Z}$ a square-free integer. If $\left(\frac{a}{p}\right)\ne +1$, then a cannot be a square modulo p².

Proof.

If $p\nmid a$, then $\left(\frac{a}{p}\right)\ne +1$; along with Proposition 1, this gives that a is not a square modulo p².

If $p|a$, then $p\left|\right|a$ because a is square-free. Assume that a is a square modulo p², i.e., $x^2\equiv a(\text{mod}{p}^2)$ for some $x\in \mathbb{Z}$. Then we have $p^2|(x^2-a)$, i.e., $p|(x^2-a)$.

Since $p|a$ and $p|(x^2-a)$, we have that $p|x^2$ implying $p^2|x^2$. However, $p^2|(x^2-a)$ and $p^2|x^2$ gives that $p^2|a$, contradicting that a is square-free. Therefore, a cannot be a square modulo p². $■$

Lemma 3.

Let p be a prime number, $k,n\in \mathbb{N}$, and $f(x)={\prod }_{i=1}^n(x^2-a_i)\in \mathbb{Z}[x]$. If $x^2-a_i\equiv 0(\text{mod}{p}^k)$ is not solvable for any $1\le i\le n$, then $f(x)\equiv 0(\text{mod}{p}^{kn})$ is not solvable.

Proof.

For the sake of contradiction, assume that $f(x)\equiv 0(\text{mod}{p}^{kn})$ is solvable for some $x\in \mathbb{Z}$, i.e., $p^{kn}|(x^2-a_1)\cdots (x^2-a_n)$. Then we must have $p^k|(x^2-a_j)$, for some $j\in \{1,2,\dots ,n\}$.

However, $p^k|x^2-a_j$ implies that $x^2-a_j\equiv 0(\text{mod}{p}^k)$ is solvable, a contradiction to the fact that $x^2-a_i\equiv 0(\text{mod}{p}^k)$ is not solvable for any i. Therefore, we have the result. $■$

4 Proof of Theorem 1

Proof of necessity

The necessity of the condition 1(a) immediately follows from Lemma 1. Now we will show that if condition 1(b) or condition 2 fails then f fails to have a root modulo some integer.

Assume that the condition 1(b) in Theorem 1 fails: if T is a subset of $\{1,2,\dots ,n\}$ of odd cardinality for which $\prod _{j\in T}{a}_j$ is a perfect square, then there exists $j\in T$ and an odd prime $p|a_j$ such that $\left(\frac{a_i}{p}\right)\ne +1$ for any $i\ne j$. Since each a_i is square-free, Lemma 2 implies that for any $i\ne j,x^2-a_i\equiv 0(\text{mod}{p}^2)$ is not solvable. Similarly, $x^2-a_j\equiv 0(\text{mod}{p}^2)$ is not solvable because $\left(\frac{a_j}{p}\right)=0\ne +1$.

Since $x^2-a_i\equiv 0(\text{mod}{p}^2)$ is not solvable for any $1\le i\le n$, Lemma 3 with k = 2 implies that the congruence $f(x)\equiv 0(\text{mod}{p}^{2n})$ is not solvable.

If condition 2 in the statement of Theorem 1 fails, then none of the a_i is equal to $8m+1$ for any nonzero $m\in \mathbb{Z}$. Since each of the a_i is square-free, part (b) of Proposition 2 implies for any $i\in \{1,2,\dots ,n\},x^2-a_i\equiv 0(\text{mod}8)$ is not solvable. Then applying Lemma 3 with p = 2 and k = 3 gives that the congruence $f(x)\equiv 0(\text{mod}{8}^n)$ is not solvable.

Proof of sufficiency

As a consequence of the Chinese remainder theorem, it suffices to show that $f(x)\equiv 0(\text{mod}{p}^b)$ is solvable for every prime p and every integer $b\ge 1$.

If p is an odd prime that does not divide $\prod _{j\in T}{a}_j$, an application of Lemma 1 for ${\left\{a_j\right\}}_{j\in T}$ implies that for some $j_0\in T,a_{j_0}$ is a square modulo p. Since $p\nmid \prod _{j\in T}{a}_j$, Proposition 1 implies that $a_{j_0}$ is a square modulo every positive power of p. Therefore, $f(x)\equiv 0(\text{mod}{p}^b)$ is solvable for every integer $b\ge 1$.

If p is an odd prime dividing $\prod _{j\in T}{a}_j$, then $p|a_j$ for some $j\in T$. Condition 1(b) of Theorem 1 ensures that there exists $i\ne j$ such that $\left(\frac{a_i}{p}\right)=+1$. Since $\left(\frac{a_i}{p}\right)=+1$, we have that $p\nmid a_i$. Therefore, a_i is a square modulo all powers of p, using Proposition 1. Hence, $f(x)\equiv 0(\text{mod}{p}^b)$ is solvable for every integer $b\ge 1$.

If p = 2, then condition 2 of Theorem 1 ensures that for some $k\in \{1,2,\dots ,n\}$ and for some nonzero integer m, $a_k=8m+1$. Then $x^2-a_k\equiv 0(\text{mod}{2}^b)$ is solvable for every $b\ge 1$, by part (b) of Proposition 2. Therefore, $f(x)\equiv 0(\text{mod}{2}^b)$ is solvable for every integer $b\ge 1$.

5 Corollaries and Examples

The first corollary gives a necessary and sufficient condition for the polynomial $(x^2-p)(x^2-q)(x^2-pq)$ to have roots modulo every positive integer. Here p and q are distinct odd primes.

Corollary 1.

Let p and q be distinct odd primes. The polynomial$$f(x)=(x^2-p)(x^2-q)(x^2-pq)$$has roots modulo every positive integer if and only if $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)=+1$.

Proof.

Note that $p\times q\times pq={(pq)}^2$ and that one of p or q or pq has to be of the form $8m+1$ for $0\ne m\in \mathbb{Z}$. So the result follows by applying Theorem 1 to $a_1=p,a_2=q$, and $a_3=a_1{a}_2=pq$. $■$

When p and q are distinct primes such that $p\equiv q\equiv 1(\text{mod}4),\left(\frac{p}{q}\right)=+1$ if and only if $\left(\frac{q}{p}\right)=+1$. Hence, the polynomial $h(x)=(x^2-p)(x^2-q)(x^2-pq)$ has roots modulo every integer when $p\equiv q\equiv 1(\text{mod}4)$ and $\left(\frac{p}{q}\right)=+1$, as mentioned in the Introduction.

Corollary 2.

Let c and d be two square-free integers not equal to 1, $c_1=\frac{c}{\text{gcd}(c,d)}$, and $d_1=\frac{d}{\text{gcd}(c,d)}$. Then $f(x)=(x^2-c)(x^2-d)(x^2-c_1{d}_1)$ has roots modulo every integer if and only if the following conditions are satisfied:

1. For each odd prime p dividing c, $\left(\frac{d}{p}\right)=+1$ or $\left(\frac{c_1{d}_1}{p}\right)=+1$ and for each odd prime p dividing d, $\left(\frac{c}{p}\right)=+1$ or $\left(\frac{c_1{d}_1}{p}\right)=+1$.

2. At least one of c, d and $c_1{d}_1$ is of the form $8m+1$ for some nonzero integer m.

Necessary and sufficient conditions for the polynomial in the above corollary to have a root modulo every positive integer were obtained by Hyde and Spearman in [5]. In our Corollary 2, there are fewer conditions to check compared to the result obtained in [5].

Proof.

Apply Theorem 1 for three square-free integers $a_1=c,a_2=d$, and $a_3=c_1{d}_1$ and note that $a_1\times a_2\times a_3=c\times d\times c_1{d}_1={(r{c}_1{d}_1)}^2$, where $r=$ gcd (c, d). $■$

It is instructive to see some examples of application of Theorem 1. The polynomials listed below are obtained from different values of n and square-free integers $a_1,a_2,\dots ,a_n$ in Theorem 1.

1. $(x^2-13)(x^2-17)(x^2-221)$ has roots modulo every integer because$$13\times 17\times 221={(221)}^2,\left(\frac{13}{17}\right)=+1,\left(\frac{17}{13}\right)=+1,\text{and}17=8(2)+1.$$

2. $(x^2-7)(x^2-11)(x^2-19)(x^2-31)(x^2-209)$ has roots modulo every integer because$$11\times 19\times 209={(209)}^2,\left(\frac{31}{11}\right)=+1,\left(\frac{7}{19}\right)=+1,\mathrm{}\text{and}\mathrm{}209=8(26)+1.$$

3. $(x^2-7)(x^2-11)(x^2-19)(x^2-31)(x^2-45353)$ has roots modulo every integer because$$7\times 11\times 19\times 31\times 45353={(45353)}^2,\left(\frac{11}{7}\right)=+1,\left(\frac{31}{11}\right)=+1,\left(\frac{7}{19}\right)=+1,\left(\frac{19}{31}\right)=+1,\text{and}\mathrm{}45353=8(5669)+1.$$

6 Discussion

Readers may notice that if f has a root modulo every positive integer, then for any integer c, $g(x):=f(x)(x^2-c)$ also has a root modulo every positive integer. This raises the question whether there exists a polynomial

$f(x)=(x^2-a_1)\cdots (x^2-a_n)$ such that

1. f has roots modulo every positive integer, but

2. every proper divisor of f fails to have a root modulo some positive integer.

This question is answered in the affirmative in [7]. Moreover, for every $n\ge 4$, there exists infinitely many polynomials of the form $f(x)=(x^2-a_1)\cdots (x^2-a_n)$ that satisfy Properties 1 and 2 (see [7]).

Acknowledgments

I am grateful to the editor and the anonymous referees for their valuable suggestions and comments. This work was partly supported by the NSF, under grant DMS-1812028.