MathJax

Syntax Highlighter CSS (shCore.css)

Syntax Highlighter CSS (shThemeDefault.css)

Syntax Highlighter JS (shCore.js)

Syntax Highlighter JS (shAutoloader)

Highlight CSS (default.css)

Highlight JS (highlight.pack.js)

Syntax Highlighter CSS (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))$$

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