Does the equation $x^2+x=a$ have an integer solution?

Question

I am writing a paper on the topological structure of the Golomb space (defined here) and arrived to the following question:

Question 1. Is it true that for a number $a\in\mathbb N$ the equation $x^2+x=a$ has an integer solution $x$ if and only if for any number $b\in\mathbb N$, coprime with $a$, the equation $x^2+x=a \mod b$ has a solution $x$ (i.e., a solution in the ring $\mathbb Z/b\mathbb Z$).

In fact, I need a more general fact.

Question $2^n$. Is it true that for any number $n\ge 0$ and any number $a\in\mathbb N$ the equation $(x^2+x)^{2^n}=a$ has an integer solution $x$ if and only if for any number $p\in\mathbb N$, coprime with $a$, the equation $(x^2+x)^{2^n}=a \mod p$ has a solution $x$ (i.e., a solution in the ring $\mathbb Z/p\mathbb Z$).

We can also ask a more general

Problem. For which monic polynomials $f\in\mathbb Z[x]$ the following local-to-global principle holds:

$(*)$: for every $b\in\mathbb N$ the equation $f(x)=a$ has a solution in $\mathbb Z$ if and only if for any $b\in\mathbb N$, relatively prime with $a$ the equation $f(x)=a \mod b$ has a solution in the ring $\mathbb Z/b\mathbb Z$?

Remark. I have edited the second question a little bit.

Answer 1

The answer is yes, and in general if $f(x)\in\mathbb{Z}[x]$ is a monic irreducible polynomial whose Galois group contains a cycle of length $\deg f$ (which is always the case when $\deg f$ is prime, by Cauchy's theorem), then for infinitely many primes $p$ the reduction $f(x)\bmod p$ is irreducible over $\mathbb{F}_p$. This follows from the Chebotarev density theorem, or the earlier Frobenius density theorem, applied to the splitting field of $f(x)$. The converse is also true and easier to prove: if $f(x)\bmod p$ is irreducible over $\mathbb{F}_p$ for any prime $p$ (which necessarily does not divide the discriminant of $f(x)$), then its Galois group contains a cycle of length $\deg f$, namely (as a conjugacy class) the Frobenius automorphism at $p$.

With the help of Burnside's lemma, one can address the number of zeros modulo $p$ in general. If $f(x)\in\mathbb{Z}[x]$ is any monic irreducible polynomial, then the average number of zeros of $f(x)$ modulo $p$, as $p$ varies over the primes, equals $1$. In fact this was proved by Kronecker in 1880 before the theorems of Frobenius and Chebotarev! For a positive density of primes $p$, the number of zeros modulo $p$ equals $d$, hence also for a positive density of primes $p$, there are no zeros modulo $p$.

For related facts and interesting history, I recommend reading Lenstra-Stevenhagen: Chebotarev and his density theorem.

Added. Upon the OP's request, let me add some textbook references. The density theorems of Frobenius and Chebotarev are proved in Janusz: Algebraic number fields (Theorems 5.2 and 10.4). The Chebotarev density theorem is treated in many other textbooks, e.g. in Lang: Algebraic number fields (Theorem 10 in Section VIII.4) or Neukirch: Algebraic number theory (Theorem 13.4). The most transparent way to prove Chebotarev's density theorem is through Artin $L$-functions, but this requires more preparation. Specifically, by Brauer's induction theorem, Artin $L$-functions are meromorphic on $\mathbb{C}$ with no pole or zero in $\Re(s)\geq 1$, except for the Riemann zeta function which has a simple pole at $s=1$. Using this fact, Chebotarev's density theorem follows in much the same way as Dirichlet's theorem on primes in arithmetic progressions. This approach is explained in Iwaniec-Kowalski: Analytic number theory; see Section 5.13 for more details, and note that the proof of (5.108) only needs (5.106).

Answer 2

Let me try to answer the more general problem.

First, there will probably not be any useful statement if the polynomial is not monic. The reason is that it is almost impossible to distinguish a rational root from an integer root, as is shown by examples like $(2x-1) (x^2+1)$ where the first factor has roots modulo every prime but $2$, and the second factor has roots mod $2$, but neither factor has integer roots.

Second, there are issues with certain special Galois groups. One example is $(x^2-2)(x^2-3)(x^2-6)$. The point is that if $a$ and $b$ are nonsquares in $\mathbb F_p$, then $ab$ is always a square. A lower-degree example is $(x^3+x+1)(x^2+ 31)=0$. If the cubic has no roots mod a prime, its discriminant must be a perfect square.

The way to avoid this is to put some condition on the Galois group of the polynomial that forces the implication "every element of the Galois group fixes some point $\implies$ some point is fixed by every element of the Galois group" to hold. This holds fine for subgroups of $S_2,S_3,S_4$ and thus the implication on roots holds for monic polynomials of degree at most $4$.

Answer 3

$a$ is an integer of the form $x^2+x$ iff $4a+1$ is a perfect square. We have the following result:

Theorem: Integer $N$ is a perfect square iff it is a square modulo every prime.

Proof: This is true for any $N\in\mathbb Z$, but let me assume it's positive and odd for simplicity.

Left to right is clear, so assume $N$ is not a perfect square. We may assume $N$ is squarefree, so write $N=p_1\dots p_r,r\geq 1$, where $p_i$ are pairwise distinct and odd. Consider the system of congruences $p\equiv 1\pmod 4,p\equiv 1\pmod p_i$ for $i=1,\dots, r-1$, $p\equiv n\pmod p_r$, where $n$ is any quadratic nonresidue modulo $p_r$. This system of congruences has a solution by Chinese remainder theorem (which reduces it to a single congruence condition modulo $4N$) and Dirichlet's theorem on primes in arithmetic progressions. By quadratic reciprocity, $p_1,\dots,p_{r-1}$ are squares modulo $p$ and $p_r$ isn't, so $N=p_1\dots p_r$ is not a square modulo $p$. Q.E.D.

For your general problem we need to delve into the world of higher reciprocity laws, class field theory and Chebotarev's density theorem, but I'm afraid I don't know enough about the topic to give a satisfactory answer. Let me just mention the following generalization of the above theorem, commonly given as a corollary to Eisenstein's reciprocity:

Theorem: Integer $N$ is a perfect $p$-th power iff it is a $p$-th power modulo all primes.

The proof is similar as above, but necessarily slightly more complicated, due to the need of a more complicated result.