A well-known old problem is to find a polynomial function, $f(x)$, such that, for each positive integer $n = 1,2,3,...,$ the result $f(n)$ is prime. Notice that if such a function exists, then one would have an alternate proof of the infinitude of primes, since there must be infinitely different outputs among the numbers $f(1),f(2),f(3),....$ (a) Prove the last statement. That is, assume that an nth degree polynomial only generated finitely many different values among $f(1),f(2),f(3)$,... and derive a contradiction.

My attempt:

Assume a finite number of primes. Then we say that there are $n$ primes, and we can list them in order: let $2=p_1<p_2<p_n$ be all primes. Now we define an integer $N=1+p_1*p_2*....*p_2$. Since $N>p_n$ and $p_n$ is the larget prime, $N$ is not prime. However, by the fundamental theorem of arithmetic (using the lemma $N>1)N$ must have a prime factor. This means of the primes in our list must divide $N$, In other words there exist an integer $i$ with $1\le i \le n$ such that $p_i$ divides $N$. Since $p_i$ divides both $N$ and the products of all the primes; it must also divide $N-p_1*p_2*...*p_n=1$. Since $p_i\ge 2$ it is impossible that $p_i$ divides one. Hence, a contradiction.

I wrote this up and presented it to my professor he stated that it does not address the point of polynomial functions. I don't think i am seeing this question correctly. Can anyone assist in the proof to address the problem.


marked as duplicate by Bill Dubuque elementary-number-theory Aug 4 '17 at 2:18

This question was marked as an exact duplicate of an existing question.

  • 1
    $\begingroup$ not all primes are necessarily on the polynomial just infinitely many. also you disprove the whole thing if you allow a constant term because by polynomial remainder theorem you can show that f(c) has the same remainder as f(0)=c when dividing by c. so not all terms can be prime ( unless all terms are constant or all terms that would normally divide by f(n) are f(n)). $\endgroup$ – user451844 Aug 4 '17 at 1:56
  • $\begingroup$ $f(x) = 2$ is a polynomial for which $f(n)$ is prime, but outputs only finitely many primes (only one!). $\endgroup$ – mephistolotl Aug 4 '17 at 2:09
  • 1
    $\begingroup$ Nowhere in your proof do you mention a polynomial. You do prove that there are infinitely many primes, but you don't do it with polynomials. $\endgroup$ – mephistolotl Aug 4 '17 at 2:11
  • $\begingroup$ See also this answer. $\endgroup$ – Bill Dubuque Aug 4 '17 at 2:27