8
$\begingroup$

I recently stumbled across this question in a test.

Paul says that "$n^2+n+1$ is prime $\forall\:n\in \mathbb{N}$".

  • Paul is correct, because...
  • Paul is wrong, because...

The answers sheet says that "all answers providing a valid counterexample, e.g. $n=4$, are valid; however, I'm interested in understanding why - is there some sort of theorem which can predict whether a polynomial is prime or not?

What I tried was:

$n^2+n+1$ can be factorized as $(n+\frac{1+\sqrt{3}i}{2})(n+\frac{1-\sqrt{3}i}{2})$. Neither of these factors is a suitable factor (i.e. is natural, different from $1$, and different from $n^2+n+1$) for any $n\in\mathbb{N}$, therefore $n^2+n+1$ must be prime $\forall\:n\in\mathbb{N}$.
Instead, $n^2-1$ can be factorized as $(n+1)(n-1)$. The factor $(n+1)$ is a suitable factor (i.e. natural, different from $1$, and different from $n^2-1$) for $n>2$; therefore, $n^2-1$ is not prime for $n>2$.

However, the above reasoning is clearly wrong, because "$n^2+n+1$ is prime $\forall\:n\in\mathbb{N}$" doesn't hold for the case $n=4$.
What is wrong in the reasoning? Can one tell whether a polynomial $p(n)$ is prime for all $n$ a priori?

$\endgroup$
  • 4
    $\begingroup$ Counterexample clearly is a formal proof. Furthermore, for quite a lot of small $n$ (like $n \leq 40$, IIRC - could be wrong), such numbers are prime. $\endgroup$ – Marcin Łoś May 15 '14 at 14:32
  • $\begingroup$ @MarcinŁoś thanks for pointing that out. I edited the question to better suit what I'm asking for. $\endgroup$ – Giulio Muscarello May 15 '14 at 14:36
  • 5
    $\begingroup$ It was established by Goldbach that there is no polynomial with integer coefficients that can give a prime for all integer inputs. Ref: mathworld.wolfram.com/Prime-GeneratingPolynomial.html $\endgroup$ – Joel May 15 '14 at 14:44
23
$\begingroup$

Hint $\ \ f(1)=3\,\Rightarrow\, 3\mid f(1\!+\!3n),\ $ e.g. $\,3\mid f(4)=21$

Remark $\ $ Above we used the Polynomial Congruence Theorem

$\ {\rm mod}\ 3\!:\ \color{}{1\!+\!3n\equiv 1}\,\Rightarrow\, f(\color{}{1\!+\!3n})\equiv f(\color{}1)\equiv 0,\ $ for all $\,f\in\Bbb Z[x]$

Alternatively $\,\ 3n\mid f(1\!+\!3n)-f(1)\ $ by the Factor Theorem $\,x-y\mid f(x)-f(y)$

The idea generalizes to a proof that any nonconstant polynomial $\in\Bbb Z[x]\,$ has a non-prime value.

$\endgroup$
14
$\begingroup$

Just because a polynomial $f$ doesn't factor doesn't mean that the number $f(m)$ you get when evaluating $f$ at a number $m$ doesn't factor. The simplest example is something like $f(x) = x+1$. This polynomial is irreducible, hence doesn't factor, but $f(3) = 4$ is clearly composite.

Here is a link showing that no polynomial with integer coefficients can evaluate to primes for all integers.

$\endgroup$
6
$\begingroup$

You want to disprove a statement of the form $\forall n\colon f(n)\text{ is prime}$, that is you want to prove $\neg\forall n\colon f(n)\text{ is prime}$, which is equivalent to $\exists n\colon \neg(f(n)\text{ is prime})$. Therefore, a counterexample is often the easiest and most straightforward way to disprove a general statement. In fact, any proof that merely shows that a $\forall$ statement is wrong without constructing a counterexample (or essentially doing so, but leaving out the details) is frowned upon by some mathematicians as being non-constructive. That being said, maybe you'd like a proof that there is no polynomial $f$ such that $f(n)$ is prime for all $n\in \mathbb N$ (except constant polynomials):

Let $$f(n)=a_dx^d+a_{d-1}x^{d-1}+\ldots+a_1x+a_0$$ be a polynomial of degree $d\ge 1$ with coefficients $a_i\in\mathbb C$, $0\le i\le d$, and $a_d\ne 0$. First we observe tat in fact $a_i\in \mathbb Q$ for all $i$: By plugging in $x=1, 2, \ldots, d+1$, we obtain $d+1$ rational equations in the unknowns $a_i$. Since the powers of $x$ are linearly independant (or look up Vandermonde matrix), there exists a unique solution, which must be rational. Then there exists $M\in\mathbb N$ sich that $a_iM\in\mathbb Z$ for all $i$. By assumption, $Mf(n)$ is $M$ times a prime for all $n\in\mathbb N$. For each prime $p$, there are at most $d$ values of $n$ such that $f(n)=p$. Since $M$ has only finitely many prime factors, $f(n)\mid M$ for only finitely many $n$. Therefore there exists $n$ such that $p:=f(n)\not\mid M$. By reducing $Mf(X)$ modulo $p$, we see that $Mf(n+kp)\equiv 0\pmod p$ for all $k\in\mathbb Z$. This implies that the prime $f(n+kp)$ is $p$ for all $k$. Especially, there are more than $d$ values of $n$ for which $f(n)=p$, contradiction. $_\square$


Trivia remark: On the other hand, there exists a polynomial in several variables with the property that its values are either negative or prime, and all primes occur!

$\endgroup$
  • $\begingroup$ Your trivia remark is really cool! Do you have a link/reference? $\endgroup$ – André 3000 May 15 '14 at 15:22
  • 1
    $\begingroup$ Here is a link to an early paper by Jones et al, not long after Matiyasevich proved existence. The $25$ variables has gone down a lot since then, I think to about $9$. $\endgroup$ – André Nicolas May 15 '14 at 15:38
  • $\begingroup$ @AndréNicolas That's cool - so instead of letters we can now use digits to index the variables :) $\endgroup$ – Hagen von Eitzen Dec 7 '16 at 17:09
5
$\begingroup$

No. For $n=43$, $n^2+n+1=1893$ which is divisible by $3$.

$\endgroup$
  • 2
    $\begingroup$ "What is wrong in the reasoning? What is a correct proof that a given polynomial $p(n)$ is (or isn't) prime for all natural numbers n?" Please read the entire question before answering. What I'm looking for is not a counterexample, but rather a proof. $\endgroup$ – Giulio Muscarello May 15 '14 at 14:32
  • 4
    $\begingroup$ @GiulioMuscarello I understand you don't find this answer satisfying, but it's in fact perfectly valid proof. $\endgroup$ – Marcin Łoś May 15 '14 at 14:34
  • 2
    $\begingroup$ @MarcinŁoś Sure, but the OP already had a much smaller counterexample with $n=4$. I don't see what this answer really adds. $\endgroup$ – André 3000 May 15 '14 at 14:38
  • 4
    $\begingroup$ Jika is probably thinking of $n^2-n+41$, which is prime for $0 \le n \le 40$ $\endgroup$ – Robert Israel May 15 '14 at 15:06
  • $\begingroup$ @RobertIsrael Yes you are right. Even though, I was thinking of Euler's formula $n^2-n+41$, I found that $43$ is a counter example. I hesitate to post my answer but since it is a valid mathematical proof I did post it. $\endgroup$ – Jika May 15 '14 at 15:15
5
$\begingroup$

Modulo 3, that polynomial is equivalent to some well known polynomial $(n-1)^2$ $$(n-1)^2=n^2-2n+1\equiv n^2+n+1 [3]$$

Hence if $n=1+3k$ for any $k$ (so each time $n-1\equiv 0[3]$) then $n^2+n+1$ will have 3 as a divisor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.