Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 15 down vote accepted

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

share|improve this answer
    
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 at 13:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.