Custom CSS

Sunday, August 2, 2009

There exists no polynomial with integer coefficients that generates only primes

Thinking back to my post about Project Euler's problem #27, this result popped into my head again. It is somewhat relevant, but the topic escaped my mind before I finished writing the previous post.

Anyways, the proof is very very simple. Assume that, on the contrary, such a polynomial exists. Call it $$f(x)$$:

$$f(x) = a_{k}x^{k}+a_{k-1}x^{k-1}+ \ldots +a_{2}x^{2}+a_{1}x+a_0$$

By assumption, if $$b$$ is an integer, $$f(b)$$ is some prime $$p$$. Let $$t$$ be an integer; then $$b+tp$$ is also an integer, and $$f(b+tp)$$ should also be prime. We can rewrite $$f(b+tp)$$ as:

$$f(b+tp) = a_{k}(b+tp)^{k} + a_{k-1}(b+tp)^{k-1} + \ldots + a_2(b+tp)^2 + a_1(b+tp) + a_0$$
$$\hspace{4em} = a_kb^k + a_{k-1}b^{k-1} + \ldots + a_2b^2 + a_1b + a_0 + p \cdot g(t)$$

...where $$g(t)$$ is some polynomial in $$t$$. The above expression can further be simplified to:

$$f(b+tp) = f(b) + p \cdot g(t)$$
$$\hspace{4em} = p + p \cdot g(t)$$
$$\hspace{4em} = p \cdot (1 + g(t))$$ the result that $$p$$ divides $$f(b+tp)$$. Given that $$f(b+tp)$$ is prime and $$p$$ divides it, we must have that $$p = f(b+tp)$$. Since $$t$$ is an arbitrary integer, it must be the case that $$f(x)$$ generates the prime $$p$$ infinitely many times.

This is a contradiction as $$f(x)$$ is a polynomial of degree $$k$$; it can take on the same value at most $$k$$ times.
Post a Comment