x^2+x+41, or more on the Minkowski bound

The big punchline of my class on quadratic imaginary number theory was that x^2+x+c produces primes for small values of x if and only if the ring of integers in the corresponding number field has unique factorization. This is already an awesome result, but what makes it truely astounding is that the meaning of “small” is different in the two directions of the theorem. That is, for the case of c=41 say, the theorem goes x^2+x+41 is prime for 0 \leq x \leq 6 implies that R has unique factorization which implies that x^2+x+41 is prime for 0 \leq x \leq 39.

The proof of this is surprisingly easy, once you know the material from my last post. First off, let’s fix some notation. Let z be a root of the polynomial y^2+y+c, and let R = \mathbb{Z}[z]. Let’s prove that x^2+x+c is prime for 0 \leq x < B implies that R has unique factorization (where B is the Minkowski bound). We need only show that every rational prime smaller than B stays prime in R. That is, we need only show that the polynomial y^2+y+c has no roots modulo p. Suppose it did have a root x, we can obviously assume that 0 \leq x < p \leq B. So x^2+x+c must be prime by assumption. However, it is a multiple of p, hence x^2+x+c = p. But x^2+x+c \geq c, which is a contradiction

Now let’s show that R having unique factorization implies that x^2+x+c is prime for 0 \leq x \leq c-2. Suppose that x^2+x+c were composite for some x with 0 \leq x \leq c-2. Then let p be the smallest prime factor of x^2+x+c. From the bound, it is easy to see that p < 41. Since x^2+x+c = 0 \mod p, we see that p is not prime in R. Hence, since R has unique factorization, p must factor in R. It is easy to see that this means p must be the norm of something in R. But, there’s nothing that has a nonsquare norm smaller than 41.

(Again, thanks to Jared Weinstein for explaining a bunch of this to me.)