# Euler's remarkable prime-producing polynomial and quadratic UFDs

Good example of a polynomial which produces a finite number of primes is: $$x^{2}+x+41$$ which produces primes for every integer $0 \leq x \leq 39$.

In a paper H. Stark proves the following result: $X_{n}$ (the ring of "algebraic integers" in $\mathbb Q(\sqrt{-n}))$ is a principal ideal domain for positive $n$ if and only if $n = 1,2,3,7,11,19,43,67,163.$ For a reference one can see:

Harold Stark, A complete determination of the complex quadratic fields of class-number one, Michigan Math J., 14 (1967) 1-27.

Consider in general the polynomial $x^{2}+x + K= (x+ \alpha)(x+ \bar{\alpha})$ which we can factorize where $\alpha$ is given by $$\alpha = \frac{{1} + \sqrt{1-4K}}{2}, \quad \bar{\alpha} = \frac{1 - \sqrt{1-4K}}{2}.$$

One can get some relationships between polynomials which produce prime in the field $\mathbb Q(\sqrt{-n})$.

Question is if a polynomial produces a prime, then will $X_{n}$ as defined above be a PID?

-

THEOREM $\$ The polynomial $\rm\ f(x)\ =\ (x-\alpha)\:(x-\alpha')\ =\ x^2 + x + k\$ assumes only prime values for $\rm\ 0\ \le\ x\ \le\ k-2 \ \iff\ \mathbb Z[\alpha]\$ is a PID.

HINT $\ (\Rightarrow)\$ Show all primes $\rm\ p \le \sqrt{n},\; n = 1-4k\$ satisfy $\rm\ (n/p) = -1\$ so no primes split/ramify.

For proofs, see e.g. Cohn, Advanced Number Theory, pp. 155-156, or Ribenboim, My numbers, my friends, 5.7 p.108. Note: both proofs employ the bound $\rm\ p < \sqrt{n}\$ without explicitly mentiioning that this is a consequence of the Minkowski bound - presumably assuming that is obvious to the reader based upon earlier results. Thus you'll need to read the prior sections on the Minkowski bound. Compare Stewart and Tall, Algebraic number theory and FLT, 3ed, Theorem 10.4 p.176 where the use of the Minkowski bound is mentioned explicitly.

Alternatively see the self-contained paper [1] which proceeds a bit more simply, employing Dirichlet approximation to obtain a generalization of the Euclidean algorithm (the Dedekind-Rabinowitsch-Hasse criterion for a PID). If memory serves correct, this is close to the approach originally employed by Rabinowitsch when he first published this theorem in 1913.

[1] Daniel Fendel, Prime-Producing Polynomials and Principal Ideal Domains,
Mathematics Magazine, Vol. 58, 4, 1985, 204-210

-
Excellent!! – anonymous Aug 16 '10 at 18:55
I worked through this problem after seeing this post, see here for a writeup: holdenlee.wordpress.com/2014/03/16/prime-producing-polynomials – Holden Lee Mar 16 '14 at 13:44