On Euler's polynomial $x^2+x+41$

Question

This is an elementary question about something way outside my area of expertise. A well-known observation due to Euler is that the polynomial $P(x)=x^2+x+41$ takes on only prime values for the first 40 integer values of $x$ starting with $x=0$, namely the values $41,43,47,53,61,71,83,\cdots,1601$. In particular this gives a rather long sequence of primes such that the differences between successive terms form an arithmetic progression, namely $2,4,6,\cdots$, which is a consequence of $P(x)$ being quadratic. All this is related to the fact that the discriminant of $x^2+x+41$ is $-163$ and the field ${\mathbb Q}(\sqrt{-163})$ has class number 1.

Suppose one asks about the next 40 values of $P(x)$ after the value $P(40)=41^2$. We have $P(41)=1763=41\cdot 43$, also not a prime. After this the next two values $P(42)=1847$ and $P(43)=1933 $ are primes. Then comes $P(44)=2021=43\cdot 47$, then four primes, then $P(49)=2491=47\cdot 53$, then six primes, then $P(56)=3233=53\cdot 61$, then eight primes, then $P(65)=4331=61\cdot 71$, then ten primes, then $P(76)=5893=71\cdot 83$. The next four values are prime as well for $x=77,\ 78,\ 79,\ 80$, completing the second forty values. But then the pattern breaks down and one has $P(81)=6683=41\cdot 163$. Thus, before the breakdown, not only do we get sequences of $2,\ 4,\ 6,\ 8,\ 10$ primes but the non-prime values are the products of two successive terms in the original sequence of prime values $41,\ 43,\ 47,\ 53,\ 61,\ \cdots$. There is a simple explanation for this last fact, the easily-verified identity $P(40+n^2)=P(n-1)P(n)$, so when $n=1,2,3,\cdots$ we get $P(41)=P(0)P(1)=41\cdot 43$, $P(44)=P(1)P(2)=43\cdot47$, etc. However, this does not explain why the intervening values of $P(x)$ should be prime.

I've done an online search to find where this might be discussed, without success, so my question is, what is a reference for this curious behavior of the second 40 values of $P(x)$ (or anything related)? I'm also a little puzzled by the identity for $P(40+x^2)$, though perhaps it comes from the norm function in ${\mathbb Q}(\sqrt{-163})$.

Answer 1

Let's start by recalling the classical explanation of why the values of $P(x)$ are prime for small $x$. Suppose that $K = \mathbf{Q}(\sqrt{-D})$ has class number one, and also that $D$ is squarefree and $D \equiv 3 \bmod 8$. The latter assumption is not much of an assumption; in all other cases, the prime $2$ is either split or ramified which forces the existence (under the class number one assumption) of an element of norm $2$, and thus $D = -1$, $-2$, or $-7$. The class number one assumption also implies that $D$ must be prime. The ring of integers of $K$ are given by

$$\mathbf{Z}[\theta], \qquad \theta = \frac{1 + \sqrt{-D}}{2},$$

and the norm form is

$$N( a + b \theta) = a^2 + a b + b^2 \left(\frac{1+D}{4}\right).$$

Note that

$$P(x) = N(x + \theta) = x^2 + x + \frac{1+D}{4}$$

When $D=163$, this is Euler's polynomial. Also note that if $b = 0$, then the norm is a square, and otherwise the norm is at least $(1+D)/4$.

Claim: if $p < (1+D)/4$, then $p$ is inert in $K$. If $N(\alpha)$ is divisible by $p$ in this range, then $\alpha$ is divisible by $p$.

Proof: If $p$ was split in $K$, then it would split principally, but then there would be an element of norm $p < (1+D)/4$ which is impossible. ($p$ can't ramify because $p < D$ and $D$ is the only prime which ramifies).

Since $P(n) < ((1+D)/4)^2$ for $n < (D+1)/4 - 1$, this explains why the small values of $P(n)$ are prime. So what then about the next $(D+1)/4$ range of values?

Let's start with the following:

Claim: If $D > p$ and $p$ splits in $K$, then $p = P(n)$ for some $n$.

Proof: If $p$ splits it must be a norm of $a + b \theta$ for some $b \ge 1$. But if $b \ge 2$ then $p \ge D$.

Now consider the values of $P(n)$ for the next half of the values, namely $(D-1)/2 > n$. Note that

$$P(n) < P\left(\frac{D-1}{2}\right) = \frac{D(1+D)}{4}.$$

In particular, suppose that $P(n)$ for $n$ in this range is not prime, and it had a prime divisor $\ge D$. Then it would also have a prime divisor less than $(1+D)/4$, which is a contradiction from the discussion above (any such prime divisor would be a norm). In particular, the only prime divisors (if it is not prime) are less than $D$ - but that means exactly from the previous claim that they have the shape $P(i)$ for some value of $i$. As you observe, one has

$$P(i-1) P(i) = P\left( \frac{D-3}{4} + i^2 \right) = P(P(i) - i - 1),$$ and also: $$P(i) P(i+1) = P(P(i) + i).$$

(These are not mysterious identities, they hold for any monic quadratic polynomial.) So now the question reduces to showing why these account for all non-trivial factorizations of $P(n)$

for $(D-1)/2 > n > (D+1)/4$. From above, any such factorization is of the form

$$P(n) = P(i) \cdot C$$

for some $i < (D+1)/4$ and some other factor $C$ (which then has to be of the form $P(j)$ for some $j$ but that is not relevant).

Write $P(i) = p$ which is prime. The roots of $P(x) \bmod p$ are given by $x = i \bmod p$ and $x = -1-i \bmod p$ since the sum of the roots is $-1 \bmod p$. It follows that

$$n \equiv i, -1-i \bmod P(i).$$

Since $P(i) > (D+1)/4$, and $n < (D-1)/2$, the only possibilities are

$$n = P(i) - 1 - i, \quad n = P(i) + i,$$

because already one can easily check that

$$2 P(i) - 1 - i > \frac{D-1}{2} > n.$$

But now one sees that $n = P(i)+i$ or $P(i)-1-i$ lead exactly to the two factorizations above, and thus $P(n)$ in this range is prime except for the values coming from the above factorizations.

Answer 2

If $P(x)=N\left(x+\frac{1+\sqrt{-163}}{2}\right)$ (norm in $\mathbb Q(\sqrt{-163})$) was composite, it would follow $x+\frac{1+\sqrt{-163}}{2}$ is not prime, so it would factor into a product of two elements of $\mathbb Z\left[\frac{1+\sqrt{-163}}{2}\right]$. Clearly it's not divisible by any rational integer, so it is a product of some elements $a+b\frac{1+\sqrt{-163}}{2}$, which have norms $a^2+ab+41b^2$, with $b\neq 0$.

If $x$ is small, $b$ has to be small as well. Indeed, if $|b|\geq 2$, we get $a^2+ab+41b^2\geq 163$, and we find that if $x<81$, $b=\pm 1$ for both factors of $x+\frac{1+\sqrt{-163}}{2}$. By considering cases according to the signs of $b$ you see that you get imaginary part $1/2$ only in a handful of cases. One such case is $(a+\frac{1+\sqrt{-163}}{2})(a-\frac{1+\sqrt{-163}}{2})=a^2+40+\frac{1+\sqrt{-163}}{2}$. Computing the norms and using the symmetries of $P$ explains the identity $P(x^2+40)=P(x)P(x-1)$.

Answer 3

The Rabinowitsch criterion says that the discriminant $\Delta=-163$ is not a square modulo any odd prime $p<41$, see this nice article by Pete Clark. So every prime factor of $P(x)$ must be $\geq 41$. But for the primes $p=43,47,53,\ldots$ it is easy to find the roots of $P(x)$ mod $p$, thanks to the fact that these primes are the first values of $P(x)$. For $p=43$ the roots are $\{1,-2\}$, for $p=47$ they are $\{2,-3\}$ and so on. This provides better bounds for the possible prime factors of $P(x)$ for $x>41$ and should explain your observation.

Answer 4

Here is a completely elementary and very simple proof.

With the identity $P(A+m^2-1)=P(m-1)P(m)$ in mind, it suffices to prove that if$P(x):=x^2+x+A$ is prime for all $x\in[0,A-2]$, while $P(A+k)$ is composite for some $k\in[1,A-2]$, then $k+1$ is a complete square.

Let $p$ be the smallest prime divisor of $P(A+k)$. If we had $p<A$, then for a suitable integer $s$ we would have $A+k-sp\in[0,A-2]$, which along with $P(A+k-sp)\equiv P(A+k)\equiv 0\pmod p$ would give $p=P(A+k-sp)>A$, a contradiction.

Thus, $p\ge A$. On the other hand, $p^2\le P(A+k)<(A+k+1)^2$, implying $p\le A+k$. As a result, $0\le A+k-p\le k\le A-2$. Consequently, \begin{align*} p &= P(A+k-p) \\ &= (A+k-p)^2+(A+k-p)+A \\ &= (A+k-p+1)^2 + p - k -1, \end{align*} whence $k+1=(A+k-p+1)^2$.

---

For completeness, here is an elementary proof that if $P(x):=x^2+x+A$ is prime for all $0\le x<\sqrt{A/3}$, then in fact $P(x)$ is prime for all $0\le x\le A-2$. (Incidentally, this is Problem 6 of the 1987 International Math Olympiad.)

Let $k$ be the smallest non-negative integer such that $k^2+k+A$ is composite, and suppose for a contradiction that $\sqrt{A/3}<k\le A-2$. Denoting by $p$ the smallest prime divisor of $k^2+k+A$, we thus have $p^2\le k^2+k+A<4k^2+k$, whence $p\le 2k-1$. Indeed, $p\le k$: otherwise from $$(p-k-1)^2+(p-k-1)+A\equiv k^2+k+A\equiv 0\pmod p$$ and $$0\le p-k-1<k$$ we would obtain $p-k-1<\sqrt{A/3}$ and $(p-k-1)^2+(p-k-1)+A=p$, whence $k+1=A+(p-k-1)^2\ge A$, a contradiction. We thus conclude that $p\le k$; as a result, from $$(k-p)^2+(k-p)+A\equiv k^2+k+A\equiv 0\pmod p$$ and $$0\le k-p<k$$ we get $(k-p)^2+(k-p)+A=p$, implying $k\ge p\ge A$, a final contradiction concluding the proof.

Answer 5

Please check my post.

It indicates that the number of divisors of $x^2+x+41$ is equal to the number of lattice points of $X^2+163Y^2-2(2x+1)Y-1=0$.

This formula is transformed in this way.

$$163X^2+163^2Y^2-2\cdot163(2x+1)Y=163$$ $$163X^2+\{163Y-(2x+1)\}^2-(2x+1)^2=163$$ $$163X^2+(163Y-2x-1)^2=4x^2+4x+164$$

$X':=163Y-2x-1,\ Y':=X$ and we divide both sides by 4,

$$\frac{{X'}^2+{163Y'}^2}{4}=x^2+x+41=P(x)$$

$$N\left(\frac{X'+Y'\sqrt{-163}}{2}\right)=P(x)$$

$\frac{X'+Y'\sqrt{-163}}{2}$ is an element of $\mathbb Q(\sqrt{-163})$.

This formula indicates that the elements of $\mathbb Q(\sqrt{-163})$ with norm $P(x)$ is linked to the product pattern of two integers of $P(x)$.

The phenomenon you are interested in is based on this fact.

For example, let $x$ be $76$.

\begin{eqnarray*} P(x)&=&76^2+76+41\\ &=&1\cdot5893\\ &=&71\cdot83 \end{eqnarray*}

The number of product pattern of $P(x)$ is $2$.

On the other hand, the elements of $\mathbb Q(\sqrt{-163})$ with norm $P(x)$ (ignore sign) are

$$\frac{153+\sqrt{-163}}{2},\ 5+6\sqrt{-163}\ .$$

The number is $2$.

The left one is a trivial element $\frac{(2x+1)+\sqrt{-163}}{2}$.The other one is a non-trivial element that indicates that $P(x)$ is a composite number.