Infinitude of Primes As a Quickie

It is a common observation that very often great discoveries are made by several people or groups of people just a few days or weeks apart. This is certainly true (even trivially so) of small personal revelations. A few days ago I wrote a page on infinitude of primes that exploited a property of the polynomial $P(x)=x^{2}+x+1.$ Then yesterday I found in the latest issue of Mathematics Magazine (87 (2014)) a problem in the Quickies section (by Michael Goldenberg and Mark Kaplan) whose relevance to that page was hard to miss:

It looks like the values of Euler’s prime-generating polynomial $P(n)=n^{2}+n+41$ are mostly prime numbers or numbers with a few prime divisors. In particular, if $1\le n\le 100,$ then $87\%$ of the values of $P(n)$ are prime and $13\%$ of the values can be factored into a product of two prime numbers. Prove that, nevertheless, there is a sequence $n_k$ of natural numbers such that the prime factorization of $P(n_{k})$ has no less than $k$ factors.

Proof

The proof is by induction. Set $n_{1}=1$ and $n_{k+1}=n_{k}^{2}+40,$ for $k\ge 1.$ Then

(1)

$\begin{align} P(n_{k+1}) &= P(n_{k}^{2}+40)\\ &=(n_{k}^{2}+40)^{2}+(n_{k}^{2}+40)+41\\ &=(n_{k}^{4} +80n_{k}^{2} +1600)+ (n_{k}^{2}+40)+41\\ &=(n_{k}^{4} +82n_{k}^{2} +1681)- n_{k}^{2}\\ &=(n_{k}^{2} +41)^{2}- n_{k}^{2}\\ &=(n_{k}^{2}+n_{k} +41)(n_{k}^{2}-n_{k} +41)\\ &=P(n_{k})P(-n_{k}). \end{align}$

From here $P(n_{k+1})=P(n_{1})P(-n_{1})P(-n_{2})P(-n_{3})\cdots P(-n_{k}).$ The quickie then concludes with the remark that every factor on the right is greater than $1.$

In analogy with the earlier page, mentioned at the outset, I propose to make an additional step. Assume a prime $p$ divides both $P(n)$ and $P(-n),$ for an integer $n.$ Then also $p|2n.$ Since both $P(n)$ and $P(-n)$ are odd, $p|n.$ So, either $p=1$ or $p=41.$ It follows that, besides a single $41,$ all other factors of $P(n)$ and $P(-n)$ are distinct. Since, for integer $n,$ $P(n)\gt 41,$ they do each have other prime factors, none shared.

This can be done more generally. Let $q$ be an odd prime, and consider the polynomial $P_{q}(n)=n^{2}+n+q$ which has an important property:

$P_{q}(n^{2}+q-1)=P_{q}(n)P_{q}(-n).$

Any common factor of $P_{q}(n)$ and $P_{q}(-n)$ must divide $2n,$ and, for $n$ odd, $n.$ Thus, for $n$ odd, a common factor of $P_{q}(n)$ and $P_{q}(-n)$ needs to divide $q$ (or $1$ - which possibility may be ignored) and, therefore, be equal to $q.$ How many common factors $q$ there could be? At most $1$ because, assuming to the contrary that there are more, we observe that in that case $n$ would be divisible by $q^{2}.$ We arrive at a contradiction by noticing that, for $n=tq^2,$ each of $P_{q}(n)$ and $P_{q}(-n)$ are at most divisible by $q.$

Model now the iteration on the foregoing example:

$\begin{cases} n_{1}&=1&\\ n_{k+1}&=n_{k}^{2}+(q-1),& k\ge 1. \end{cases}$

This, in particular, means that the iterations are defined recursively: $P_{q}(n_{k+1})=P_{q}(n_{k})P_{q}(-n_{k}),$ $k\ge 1$ and, as before, $P_{q}(n_{k+1})=P_{q}(n_{1})P_{q}(-n_{1})P_{q}(-n_{2})P_{q}(-n_{3})\cdots P_{q}(-n_{k}).$ Each iteration (with one caveat) adds at most one factor $q$ and at least one other prime factor because $P_{q}(n)\gt q,$ for $n\gt >0.$ The exception occurs at the passage from $k=2$ to $k=3.$ Clearly, $n_{2}=q,$ so that $P_{q}(n_{2})=q^{2}$ and "another prime factor" is still an extra $q.$ To be on a safe side, we claim that

$P_{q}(n_{k}) = q^{s}p_{1}p_{2}\cdots p_{t},$ where $s\le k$ whereas $t\ge k-2,$ and all $p_{i}$'s are distinct.

One conclusion that can be drawn from this exercise is that the number of primes is infinite.

Infinitude of Primes

70762545