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

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})$$.

• A similar phenomeon occurs for $x^2+x+11$ and $x^2+x+17$ (which corresponds to $\mathbb{Q}(\sqrt{-43}).$ and $\mathbb{Q}(\sqrt{-67}).$). – LeechLattice Jun 10 '19 at 15:01
• I was about to say that the same observation appears in page 95 of this book draft, but I just realized you wrote it! – pregunton Jun 10 '19 at 15:05
• @pregunton, The 1st OP sentence, "This is an elementary question about something way outside my area of expertise," combined with the existence of that book draft, certainly challenge one's perception. :) – Michael Jun 10 '19 at 17:02
• As I look at this question, it has $41$ up-votes. If I vote for it, will a Sign from the supernatural realm be obscured by noise? Will the ghost of Douglas Adams take over supervising this question from Above? – Michael Hardy Jul 25 at 19:15

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?

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.

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)$$.

• If $P(x)= x^2+x+A$ then the identity $P(x)P(x-1) = P(x^2+A-1)$ is trivial to verify. It doesn't have anything to do with $163$. – Lucia Jun 10 '19 at 17:32
• @Lucia Of course I agree, but it can still be seen as coming from the norm in a quadratic field. More generally, there is an identity expressing a product of two numbers of the form $x^2+xy+Ay^2$ as another such number, which is most easily derived by looking at the form in the quadratic field $\mathbb Q(\sqrt{1-4A})$ whenever $A$ is an integer. Of course, just like the $P$ identity, the resulting identity can be immediately seen to be true algebraically, but I still think it's nice to observe that it can be explained in terms of norms (like the OP was suspecting). – Wojowu Jun 10 '19 at 18:17

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, 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}. 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 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 we get $$(k-p)^2+(k-p)+A=p$$, implying $$k\ge p\ge A$$, a final contradiction concluding the proof.

• That was a nice proposal, Professor Vsevolod! – José Hdz. Stgo. Jun 12 '19 at 20:21
• This problem is where I (and probably many other former olympians) first time saw your name. – Fedor Petrov Jul 25 at 15:18

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.

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.