The condition that Euler's prime generating polynomial is a composite number

Question

I anticipate that the number of lattice points of a special ellipse will be equal to the number of divisors of a number represented by Euler's prime generating polynomial.

Euler's prime generating polynomial: $$f(x)=x^2+x+41 \ \ \ \ \ \ \ \ x\in\mathbb{Z} $$

Special ellipse: $$X^2+163Y^2-2(2x+1)Y-1=0 \ \ \ \ \ \ \ \ \ X,Y\in\mathbb{R}$$

$$$$

For example, let $x$ be 40.

Euler's prime generating polynomial:

\begin{eqnarray*} f(40)&=&40^2+40+41\\ &=&1681\\ &=&41^2 \end{eqnarray*}

The number of divisors of $f(40)$ is equal to 3.

Special ellipse:

\begin{eqnarray*} &X^2&+163Y^2-2(2\cdot40+1)Y-1=0\\ &X^2&+163Y^2-162Y-1=0 \end{eqnarray*}

Lattice points of this special ellipse are following. $$(X,Y)=(1,0),(-1,0),(0,1)$$

The number of lattice points is equal to 3.

Please watch this video https://www.youtube.com/watch?v=i5c69-A0cEk.

If you find a counterexample or proof, please let me know.

---

I assert the following theorem related to this problem.

Theorem 1. $ \forall x, \alpha \in \mathbb{N}, \alpha \neq 1$,

The equation $$x=Yy^2+(Y+1)y+Y\alpha$$ has rational solution $y$ and natural number solution $Y$ $\Rightarrow$ $x^2+x+\alpha$ is a composite number.

Proof. We express the two rational solutions as following: $$y=\frac{n_1}{m_1},\frac{n_2}{m_2},\ \ \ \ where \ m_i\in\mathbb{N},\ n_i\in\mathbb{Z},\ gcd(m_i,n_i)=1,\ (i=1,2)$$ From the factor theorem and $gcd(Y,Y+1)=1$, we can get the following relation. $$(m_1y-n_1)(m_2y-n_2)=Yy^2+(Y+1)y+Y\alpha-x$$ $$m_1m_2y^2-(m_1n_2+m_2n_1)y+n_1n_2=Yy^2+(Y+1)y+Y\alpha-x$$

Hence \begin{eqnarray*} m_1m_2 &=& Y \\ -(m_1n_2+m_2n_1) &=& Y+1 \\ n_1n_2 &=& Y\alpha-x \end{eqnarray*}

So we can get $$x=m_1m_2\alpha-n_1n_2$$ $$m_1n_2+m_2n_1+m_1m_2=-1.$$

We combine the two equation as following: $$x=\frac{n_1n_2-m_1m_2\alpha}{m_1n_2+m_2n_1+m_1m_2}$$

We enter this $x$ into $x^2+x+\alpha$ and calculate the factorization.

We can get $$x^2+x+\alpha = \frac{(n_1^2+m_1n_1+\alpha m_1^2)(n_2^2+m_2n_2+\alpha m_2^2)}{(m_1n_2+m_2n_1+m_1m_2)^2}.$$

Since $\ m_1n_2+m_2n_1+m_1m_2=-1$, $$x^2+x+\alpha = (n_1^2+m_1n_1+\alpha m_1^2)(n_2^2+m_2n_2+\alpha m_2^2).$$

So $x^2+x+\alpha$ is a composite number. $$\tag*{$\square$}$$

---

Since $y=\frac{-Y-1 \pm \sqrt{(1-4\alpha)Y^2+2(2x+1)Y+1}}{2Y}$, we can get a condition from Theorem 1.

Lemma. $\forall x,\alpha \in \mathbb{N}$,

The ellipse $$X^2 = (1-4\alpha)Y^2+2(2x+1)Y+1, \ \ \ \ \ \ Y>0$$ has lattice points$(X,Y)$. $\Rightarrow$ $y$ is a rational number.

If $Y=0$ is allowed, the ellipse has always $(X,Y) = (\pm 1,0)\ \ $(trivial lattice points).

Hence, the following assertion is correct.

Theorem 2. $\forall x,\alpha \in \mathbb{N}, \alpha \neq 1$,

The ellipse has one or more non-trivial lattice points. $\Rightarrow x^2+x+\alpha$ is a composite number.

The following conjecture is unresolved.

Conjecture. $\forall x \in \mathbb{N} ,\ \forall \alpha \in \{3,5,11,17,41\} $,

The ellipse has only trivial lattice points. $\Leftrightarrow x^2+x+\alpha$ is a prime number.

(The ellipse has one or more non-trivial lattice points. $\Leftrightarrow x^2+x+\alpha$ is a composite number.)

If this conjecture is correct, the number of lattice points and the number of divisors are equal.

Answer 1

Some partial workings showing:

Let the lattice points $(X,Y) = (\pm 1,0)$ correspond to the divisors $1$ and $x^2+x+41$.

There exists a map from the lattice points $(X,Y)\in \mathbb Z^2$ for $X,Y\neq 0$ and $x\neq 40$ to factorizations $$ x^2+x+41 = rs,\;\;\;\;r,s\geq 2, r\neq s $$ satisfying $$ 16Y^2rs = ((X+1)^2+163Y^2)((X-1)^2+163Y^2) $$ Hence we may set $(X,Y)\mapsto r$ and $(-X,Y)\mapsto s$.

It could be non-subjective (some $r,s$ not covered) or non-injective (different lattice point mapping to same $r,s$), not sure yet. Ideally it could prove to be subjective and injective which will prove/solve the problem.

The rest below are the proofs.

---

We first remove the special case where a square factorization is possible.

Lemma 1. There is exactly one square factorization $$ x^2+x+41=r^2 $$ corresponding to $(x,r)=(40,41)$ and one lattice point $(X,Y)$ with $X=0$ corresponding to $(X,Y)=(0,1)$.

Proof. Rewritting the equation we get $$ 163 = (2r+2x+1)(2r-2x-1) $$ So $2r+2x+1=163$ and $2r-2x-1=1$. Solving gives us the unique pair $(x,r)=(40,41)$, hence there is only 1 type of square factorization $r^2=41^2$. On the other hand, if $X=0$ then $$ (163Y−2(2x+1))Y=1 $$ so $Y=\pm 1$. There are no solutions if $Y=-1$, while letting $Y=1$ gives $x=40$. Hence there is exactly one lattice point $(X,Y)$ with $X=0$ (which is $(0,1)$).

$$ \tag*{$\square$} $$

---

The case $x=40$ was already solved earlier. From now on we ignore this case, so (1) each factorization $rs$ must be $r\neq s$ and the lattice point $(X,Y)=(0,1)$ does not exist. We still associate $(\pm 1,0)$ with divisors $1,x^2+x+41$.

We now derive the map for the rest of the lattice points, the general case. This requires $Y\neq 0$ hence the special treatment for $(\pm 1,0)$.

Lemma 2. Each lattice point $(X,Y)$ with $X,Y\geq 1$ and $x\neq 40$ induces a factorization $$ x^2+x+41=rs $$ with $r\neq s$ and $r,s\geq 2$. They are related via: $$ (r,s) = \left(\frac{(X+1)^2+163Y^2}{u},\frac{(X-1)^2+163Y^2}{v}\right) $$ for some $uv=16Y^2$.

Proof. Rearranging $$ X^2+163Y^2−2(2x+1)Y−1=0 $$ gives us $$ x^2+x + 41 = \frac{((X+1)^2 + 163Y^2)((X-1)^2 + 163Y^2)}{16Y^2} $$ So we want to form two proper factors from the RHS.

Case 1: $Y$ is odd
First assume that $Y$ is odd. From $$ X^2 + 163Y^2-2(2x+1)Y-1 = 0 $$ we obtain that $X$ is even. Taking modulo $Y$: $$ (X+1)(X-1) \equiv 0 \pmod Y $$ Since $$ d = \gcd(X+1,X-1) = \gcd(X+1,2), $$ $X+1$ and $X-1$ can only have common factor $1$ or $2$. This means that we can write $Y = uv$ such that $\gcd(u,v)=1$, $u$ and $v$ divides $X+1$ and $X-1$ respectively. Let $X+1 = au$ and $X-1=bv$.

Hence $$ x^2+x + 41 = \frac{((X+1)^2 + 163Y^2)}{4u^2}\frac{((X-1)^2 + 163Y^2)}{4v^2} = \frac{(a^2+163v^2)}{4}\frac{(b^2+163u^2)}{4} $$ Since $a,b,u,v$ are all odd, we can see that both factors are actually integers (taking modulo $4$). Hence we get a non-trivial factorization $$ (r,s) = \left(\frac{a^2+163v^2}{4},\frac{b^2+163u^2}{4}\right) $$

Case 2: $Y$ is even
Next, assume that $Y$ is even. As before we get $X$ is odd. Write $Y = 2^k Z$ so that $Z$ is odd. Again from $$ (X+1)(X-1) \equiv 0 \pmod Y \implies (X+1)(X-1) \equiv 0 \pmod Z, $$ we can factor $Z=uv$ with $\gcd(u,v)=1$ such that $u$ and $v$ divides $X+1$ and $X-1$ respectively. That takes care of the odd part $Z$, but we also need to handle the $2^k$ part.

Now taking modulo $2^{k+1}$ gives us $$ (X+1)(X-1) \equiv 0 \pmod{2^{k+1}} $$ Since $X$ is odd, $2=\gcd(X+1,X-1)$. WLOG we may assume that the factors of $2$ split as $$ \begin{align*} X+1 &\equiv 0 \pmod{2^k}\\ X-1 &\equiv 0 \pmod 2 \end{align*} $$ (Both are even so $2$ divides it at least once. $\gcd = 2$ means one of them is divisible by $2$ exactly once hence the other is divisible by $2^k$. We assume this is $X+1$.)

Case 2a: $k=1$
In this case $Y=2uv$. We can set $X+1=2au$ and $X-1=2bv$, so $$ rs = \frac{(X+1)^2+163Y^2}{4u^2}\frac{(X-1)^2+163Y^2}{4\cdot 4v^2} = (a^2+163v^2)\cdot \left(\frac{b^2+163u^2}{4}\right) $$ Notice that $b,u$ are both odd so $(b^2+163u^2)/4$ is an integer. So this is a valid factorization.

Case 2b: $k\geq 2$
We need to first prove that $2$-valuation of $X+1$ is exactly $2^k$. i.e. $2^{k+1}\nmid X+1$. Suppose instead that $2^{k+1}$ divides $X+1$, then $2^{k+2}$ divides $(X+1)(X-1)$. Hence taking modulo $2^{k+2}$: $$ \begin{align*} 163Y^2-2(2x+1)Y &\equiv 0 \pmod{2^{k+2}}\\ 163u^2v^2(2^{2k})-uv(2x+1)(2^{k+1}) &\equiv 0 \pmod{2^{k+2}}\\ 163u^2v^2(2^{2k})-uv(2^{k+1}) &\equiv 0 \pmod{2^{k+2}}\\ 163u^2v^2(2^{k-1})-uv &\equiv 0\pmod 2 \end{align*} $$ Since $k\geq 2$ and $u,v$ are odd, this is a contradiction.

Therefore $X+1$ is divisible by $2$ exactly $k$ times. Let $X+1 = 2^kau$ and $X-1=2bv$ for some odd $a,b$. Hence we can form the factorization: $$ (r,s) = \left(\frac{(X+1)^2+163Y^2}{4\cdot 2^{2k}u^2},\frac{(X-1)^2+163Y^2}{4v^2}\right) = \left(\frac{a^2+163v^2}{4},b^2+163(2^{2k-2}u^2)\right) $$ Once again odd-ness of $a,v$ ensures $a^2+163v^2$ is divisible by $4$ and hence $r$ is an integer.

In all cases we derived a factorization $x^2+x+41=rs$ from a given lattice point $(X,Y)$, which completes the proof. $$ \tag*{$\square$} $$

---

Since $r\neq s$, we may set each lattice point $(X,Y)$ to "point" to $r$ and $(-X,Y)$ to "point" to $s$. It remains to show that
(1) The formation of $r,s$ is unique. This means we can't split the divisors of $16Y^2$ in other ways during Lemma 2 (the powers of $2$). This should be easy by considering the factors of $2$ more carefully.
(2) All factorizations $(r,s)$ are covered (subjectivity). Presumably working backwards to get an inverse map may work.
(3) Distinct lattice points gives rise to distinct factorizations $(r,s)$. Not sure. Edit 1: Come to think of it probably getting the inverse map (2) and showing injectivity suffices.

Answer 2

Edit 1 (2020/01/16): This now gives an injective map from distinct factorization pairs $\{r,s\}$ to distinct lattice points $(\pm X,Y)$, hence number of divisors $\leq $ number of lattice points.

---

I think I've got the other direction, but right now I can only see an easy way via Algebraic Number Theory. An elementary way seems possible but it took me a full page just to show that every prime factor has the form $a^2+163b^2=4p$. It's hard to squeeze it in here. The summary is

Theorem 1. Let $x$ be an integer an $r,s$ integers satisfying $$ x^2+x+41 = rs $$ Then there exists integers $a,b,c,d$ such that $$ \begin{align*} (r,s) &= \left(\frac{a^2+163b^2}{4},\frac{c^2+163d^2}{4}\right)\\ ac-163bd &= 2(2x+1)\\ ad+bc &= 2 \end{align*} $$ Then setting $(X,Y)=(ad-1,-bd)$ satisfies $$ X^2+163Y^2-2(2x+1)Y-1=0 $$

---

Given any integer $x$, we start with $$ x^2+x+41 = \frac{(2x+1)^2+163(1)^2}{4} = \frac{(2x+1)+w}{2}\cdot \frac{(2x+1)-w}{2} $$ where $w=\sqrt{-163}$. Let the prime factorization of $x^2+x+41$ be $$ x^2+x+41 = \prod_{k=1}^n p_i $$ where the $p_i$ may be repeated.

---

Now the key idea is, using Algebraic Number Theory, there is a unique factorization (since $\mathbb Q(w)$ has class number $1$) $$ \frac{(2x+1)+w}{2} = \pm\prod_{k=1}^n \frac{a_i+b_iw}{2} $$ where the $a_i,b_i$ satisfies $$ p_i = \frac{a_i^2+163b_i^2}{4} $$

---

To get a pairwise factorization $x^2+x+41=rs$, for each prime factor $p$ of $r$ we can pick a corresponding $(a_i+b_iw)/2$ such that $a_i^2+163b_i^2=4p$. This splits the product into two: $$ \begin{align*} \frac{(2x+1)+w}{2} &= \left(\pm\prod_{i=1}^m \frac{a_i+b_iw}{2}\right)\cdot \left(\pm\prod_{i=m+1}^n \frac{a_i+b_iw}{2}\right) \end{align*} $$ (possibly with some rearranging of the primes.) Now taking the norm, (or complex norm): $$ \begin{align*} N(\frac{(2x+1)+w}{2}) &= N\left(\pm\prod_{i=1}^m \frac{a_i+b_iw}{2}\right)\cdot N\left(\pm\prod_{i=m+1}^n \frac{a_i+b_iw}{2}\right)\\ \frac{(2x+1)^2+163}{4} &= (\prod_{i=1}^m p_i) \cdot (\prod_{i=m+1}^n p_i) = r\cdot s \end{align*} $$

---

Now comes the key part: For each of those arrangements we can rewrite the factored equation as $$ \begin{align*} \frac{(2x+1)+w}{2} &= \left(\pm\prod_{i=1}^m \frac{a_i+b_iw}{2}\right)\cdot \left(\pm\prod_{i=m+1}^n \frac{a_i+b_iw}{2}\right)\\ &= \frac{a+bw}{2} \cdot \frac{c+dw}{2} \end{align*} $$ for some integers $a,b,c,d$.

By comparing the real and imaginary parts, $$ \begin{align*} ac-163bd &= 2(2x+1)\\ ad+bc &= 2 \end{align*} $$

These are the two defining equations that gives us our lattice points: $$ \begin{align*} 0 &= 0*a + 0*b\\ &= (ad+bc-2)*a - (ac-163bd-2(2x+1))*b\\ &= a^2d-2a +163b^2d + 2(2x+1)b\\ 0 &= (ad)^2-2(ad) + 163(bd)^2+2(2x+1)(bd)\\ 0 &= (ad-1)^2 + 163(-bd)^2 - 2(2x+1)(-bd) -1 \end{align*} $$ Hence we may set $$ (X,Y) = (ad-1,-bd) $$ Finally, we note that each factorization has two factors and and there are two lattice points $(\pm X,Y)$ so this gives a two-to-two map.

---

Note: There is still a need to show that distinct $r,s$ gives rise to distinct $(\pm X,Y)$'s. I'm not sure if it's obvious.

Edit 1 (Map is injective):

Lemma 2. The map in Theorem 1 maps distinct factorization pairs $(r,s), r\leq \sqrt{x^2+x+41}$ to distinct lattice points $(\pm X,Y)$. Therefore the number of divisors of $x^2+x+41$ is lesser or equal to the number of lattice points.

Proof. Consider the set of factorizations pairs $(r_i,s_i)$ (with $r_i \leq \sqrt{x^2+x+41}$). By Theorem 1, we may write each element as $$ (r_i,s_i) = \left(\frac{a_i^2+163b_i^2}{4},\frac{c_i^2+163d_i^2}{4}\right) $$ Now since $$ a_id_i+b_ic_i = 2, $$ either $\gcd(a_i,b_i)=1$ or $\gcd(c_i,d_i)=1$. If $\gcd(a_i,b_i)=2$ then we swap $(r_i,s_i)$ to $(s_i,r_i)$. This ensures $\gcd(a_i,b_i)=1$ for all pairs.

Now we claim that the set $$ (X,Y) = (a_id_i-1, -b_id_i) $$ is distinct with no repetitions. Suppose otherwise, then $$ (a_id_i-1) = X = (a_jd_j-1), -b_id_i = Y = -b_jd_j $$ for some $i\neq j$. This gives $$ a_i/a_j = d_j/d_i = b_i/b_j \implies a_ib_j = a_jb_i $$ But since $\gcd(a_i,b_i) = 1 = \gcd(a_j,b_j)$, this gives $$ (a_i,b_i) = (a_j,b_j) $$ which would then give $r_i =r_j$, contradicting that each $r_i$ is distinct.

Therefore each factorization must map to a distinct (positive) lattice point $(X,Y)$. $$ \tag*{$\square$} $$

---

Example. We choose a random integer $x=3080456244$, giving us factorization $$ x^2+x+41 = 53\cdot 5237\cdot 3435239\cdot 9952099 $$ Next we work out the unique factorizations $a^2+163b^2=4p$. With $w=\sqrt{-163}$, this is: $$ \frac{(2x+1)+w}{2} = \left(\frac{7-w}{2}\right)\left(\frac{35-11w}{2}\right)\left(\frac{2977-173w}{2}\right)\left(\frac{-6273+53w}{2}\right) $$ Now suppose we are interesting in the factorizations $r=53\cdot 9952099,s = 5237\cdot 3435239$. Hence we rewrite the equation as $$ \begin{align*} \frac{(2x+1)+w}{2} &= \left(\frac{7-w}{2}\frac{-6273+53w}{2}\right)\cdot \left(\frac{35-11w}{2}\frac{2977-173w}{2}\right)\\ &= \left(\frac{-17636+3322w}{2}\right)\cdot \left(\frac{-102997-19401w}{2}\right) \end{align*} $$ Hence we get $$ (a,b,c,d) = (-17636,3322,-102997,-19401) $$ and a simple check shows $$ ac-163bd = 2(2x+1),\;\;\;\; ad+bc = 2 $$

Taking norms will give us $$ x^2+x+41 = \frac{(-17636)^2+163(3322)^2}{4} \cdot \frac{(-102997)^2+163(-19401)^2}{4} = (r)\cdot (s) $$ which is the correct factorization. Setting $$ (X,Y) = (ad-1,-bc) = (342156035, 64450122) $$ we can also check that $$ X^2+163Y^2-2(2x+1)Y-1 = 0 $$ which is indeed a valid lattice point.