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

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.

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.

• polynomial remainder theorem.
– user645636
Dec 23, 2019 at 15:01
• Tested up to $x=10^4$ without counterexamples, this seems likely to be true. Dec 24, 2019 at 3:37
• @YiFan coincidence, I also tested up to $x=10^4$. $(\pm 1,0)$ can be linked to divisors $1$ and $x^2+x+41$. It is not too difficult to show that a lattice pair $(X,Y)$ with $Y\geq 1$ gives rise to at least one non-trivial factorization $rs$ (so $r,s\geq 2$), so if $X\neq 0$ you can let $(-X,Y),(X,Y)$ "point" to $r$ and $s$ respectively. I think $X=0$ would correspond to $r=s$. Atlas, it seems tedious to directly show (1) distinct lattice points lead to distinct factors. (2) Exactly 1 factorization per point. (3) No factorizations were missed out (i.e. the other direction). Dec 24, 2019 at 7:58
• (cont.) If $X=0$ then it forces $Y=1$ which then forces $x=40$, which means $x^2+x+41 = 41^2$. Conversely, if $x^2+x+41=r^2$ then it can be shown that the only solution is $x=40$. Hence there is exactly one type of square factorizations $x^2+x+41=r^2$ and one type of lattice point with $X=0$. So it suffies to consider $X,Y\geq 1$ and $x\neq 40$. Dec 24, 2019 at 8:13
• I posted that as Lemma 1 below. Having $$x^2+x+41 = r^2$$ means $$163 = (2x+2r+1)(2x-2r-1)$$ and there is only one possible way: $(2x+2r+1,2x-2r-1)=(163,1)$. This gives $(x,r) = (40,41)$. Dec 24, 2019 at 10:07

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.

• It’s great. But I can’t evaluate correctly because I’m not a math expert. Dec 25, 2019 at 4:27
• Let $x\neq 40$. A summary is you can manipulate given equation to: $$16Y^2(x^2+x+41) = ((X+1)^2+163Y^2)((X-1)^2+163Y^2)$$ These are all integers so for $Y\geq 1$ it ensures there is a way to divide $16Y^2$ on both sides. Since both factors $(X\pm 1)^2+163Y^2$ are greater than $16Y^2$ (as $Y\geq 1$), no matter how the division goes you will still end up with two factors left: $$x^2+x+41 = r\cdot s$$ And then we also know $r\neq s$, otherwise it's a square factorization, which is not possible for $x\neq 40$. So guaranteed there is a mapping $(X,Y)\mapsto r$ and $(-X,Y)\mapsto s$. Dec 25, 2019 at 5:50
• Anyway it's incomplete so no worries about accepting it or not (you shouldn't). I just wanted to show that there is an injective map from the lattice points to the divisors (though still missing one step, that distinct lattice points map to distinct $r,s$). Dec 25, 2019 at 6:07
• More importantly it also helps by giving you the hint that all factors $$x^2+x+41=rs$$ should be expressible as some kind of $a^2 + 163b^2$. This seems like it might be provable by Quadratic Reciprocity. Dec 25, 2019 at 6:07
• Thank you. It’s so interesting. Dec 25, 2019 at 6:21

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.

• The answers are not so nice since they are very lengthy and quite computational. I'm sure there's a neater explanation. I'm not sure what you mean by evaluated, but currently (1) there is a map from $(r,s)$ to $(\pm X,Y)$ and also the other way round, but (2) it's not so clear yet (to me at least) that they always map to distinct outputs. Solving (2) will show that maps are strictly one-to-one so both sides must have the same number of elements, but I haven't found a nice way to do that. Jan 9, 2020 at 10:18
• I'm not sure if you noticed it, but this answer is almost the full proof. It gives you a concrete way to map each distinct divisor pair $\{r,s\}$ to a distinct lattice point pair $(\pm X,Y)$ so (1) number of divisors $\leq$ number of lattice points. (2a) The very last remaining part is to show that each $(X,Y)$ can be "reached" by that map so that it must be an equality instead and that would be the end. (2b) I almost see a direct way: let $gcd(X+1,Y)=d$, write $X=ad,Y=-bd$ then you will eventually get $$x^2+x+41 = \frac{(a^2+163b^2)(c^2+163d^2)}{16}$$but this approach seems to get lengthy... Jan 16, 2020 at 15:45
• I had a misunderstanding. It's great! . Jan 17, 2020 at 4:17
• Does this only happen when the class number is 1? Jan 17, 2020 at 5:29
• For larger class number will be different ways to factor a prime. Example if an odd prime $p$ divides $x^2+x+6$ then it can be written as $(a^2+23b^2)/k=p$ for some $1\leq k\leq 9$. I think it should turn up to be just 2 classes $a^2+23b^2=p$ or $a^2+23b^2=3p$. This is related to the fact that $\mathbb Q(\sqrt{-23})$ has class number $3$. However it may be still possible to form relationship from the factorizations, especially if you know the types of primes that can happen (maybe if you only choose certain types of $x$ only one type can happen). I'm not sure though. Jan 17, 2020 at 6:26