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

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.

• I added the analytic number theory tag, because the answers and history make it relevant. – GH from MO Dec 24 '17 at 12:22
• I would not be surprised if the answer to your Question $2^n$ is no in general. Your problem looks very similar to the Grunwald–Wang theorem. As explained in the link, 16 is an 8th power modulo every odd prime $p$, but is clearly not an 8th power in $\mathbb{Z}$. I tried to use this to give a counter-example in the case $n=3$ and $a=16$, but alas it does not seem to work as the polynomial $(x^2 + x)^8 = 16$ has no root modulo $7$. However, something like this might still work. – Daniel Loughran Dec 25 '17 at 1:08

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).

• In fact the use of Burnside's lemma is almost exactly the reverse - it can be used as part of a proof of the Frobenius density theorem from Kronecker's theorem. – Will Sawin Dec 24 '17 at 13:00
• @GHfromMO Thank you for the reference to the paper of Lenstra-Stevenhagen. It is very intertesting and helpful, a biographical part also. – Taras Banakh Dec 24 '17 at 15:43
• Why a polynomial with prime degree has cyclic Galois group? Do you assume the polynomial is Galois? – Lior Bary-Soroker Dec 25 '17 at 19:05
• The condition on the Galois group of $f(x)$ is not that it's cyclic, but rather that it contains a permutation that is one cycle (of length $\deg f$). And it indeed always holds if $\deg f$ is prime. – Jarek Kuben Dec 25 '17 at 22:08
• @LiorBary-Soroker: I updated the text according to Jarek Kuben's comment. Thanks for calling our attention to this inaccuracy! – GH from MO Dec 25 '17 at 22:30

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$.

• So in general to check there is no such obstruction to the local-global principle, we need to find each Galois group of each polynomial dividing $f$ ? – reuns Dec 25 '17 at 6:14
• @reuns It would be sufficient to find the Galois group of the polynomials $f-a$ for all $a$. However, we can potentially succeed with partial information about this set of Galois groups, depending on what the partial information is. We need to determine whether a particular implication holds for every group in this class or not. – Will Sawin Dec 26 '17 at 3:21

$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.

• For this quadratic case, once you invoke quadratic reciprocity you don't even need Dirichlet's theorem, as I already noted in this forum back in 2013: mathoverflow.net/questions/135820 – Noam D. Elkies Dec 25 '17 at 0:54