I am writing a paper on the topological structure of the Golomb space ([defined here](https://mathoverflow.net/questions/286785/)) 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. 



Does the equation $x^2+x=a$ have an integer solution?
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](https://en.wikipedia.org/wiki/Cauchy%27s_theorem_(group_theory))), 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](https://en.wikipedia.org/wiki/Chebotarev%27s_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](https://en.wikipedia.org/wiki/Burnside%27s_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](https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1996d/art.pdf).


**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](https://en.wikipedia.org/wiki/Brauer%27s_theorem_on_induced_characters), 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).


