# Is $xz+1$ a proper divisor of $a_3z^3+a_2z^2+a_1z+1$ finitely often?

Given a polynomial $$P=a_3z^3+a_2z^2+a_1z+1, z >0$$ with non-negative integer coefficients $$a_1, a_2, a_3\ne 0$$, it appears if $$P$$ is not factorizable then there are finitely many positive integers $$x, z$$ such that $$xz+1 \mid P(z)$$, $$xz+1. If $$a_2=a_1=0$$, the claim is true. The Diophantine equation $(xz+1)(yz+1)=az^{3}+1$ has no solutions in positive integers with $z > a^2+2a$. However the proof for the general case doesn't follow directly from the proof for the case $$P=a_3z^3+1$$. Also for a particular triple $$(a_1, a_2, a_3)$$, what's the minimum value of $$z$$ such that $$xz+1$$ is not a proper divisor of $$P(z)$$ for all $$x>1$$?

My thoughts: If $$P$$ is factorizable then we can find integers $$b_1, b_2, b_3$$ such that $$a_3z^3+a_2z^2+a_1z+1=(b_1z+1)(b_2z^2+b_3z+1)$$. Expanding and comparing coefficients we get $$b_1+b_3=a_1$$, $$b_1b_3+b_2=a_2$$, and $$b_1b_2=a_3$$. Since $$P$$ is assumed non-factorizable, we will have to use this result somewhere in the proof.

• Why do you want to prove that and how do you know it's true? May 5, 2021 at 20:03
• Questions in the imperative voice ("Prove that …") are usually not well received; I would suggest editing it. I'm also pretty sure that you mean that there are only finitely many such integers. \\ Also, TeX note: using | with manual spacing doesn't work well; prefer \mid. Compare, for example, the spacing of $a \not | \ b$ a \not | \ b to $a \nmid b$ a \nmid b. I have edited accordingly (but not to make the other changes I suggested). May 5, 2021 at 20:26
• Because it has application to primality testing. If this is true which is most likely the case beyond doubt then if $z$ is prime, we can prove whether $P(z)$ is prime by checking if $b^{P(z) - 1} \equiv 1 ($mod $P(z))$ and $b^{(P(z) - 1) /p} \not\equiv 1 ($mod $P(z))$. There would be no need to obtain another factor of $P(z) - 1$ required in Pocklington's test
– ASP
May 5, 2021 at 20:28
• It's most likely true because I have examined a number of cases by experiment . Also I already proved the case when $a_2=a_1=0$ which gives me more confidence
– ASP
May 5, 2021 at 20:31
• Perhaps I don't understand what you're asking. You always have $P(z) = x z + 1$ where $x = a_3 z^2 + a_2 z + a_1$. That makes infinitely many solutions. May 5, 2021 at 21:03

The conjecture is true. That is, if the integral cubic polynomial $$P(Z)=a_3 Z^3+a_2 Z^2+a_1 Z+1$$ is irreducible in $$\mathbb{Z}[Z]$$ (hence also in $$\mathbb{Q}[Z]$$ by Gauss's lemma), then there are only finitely many positive integer solutions of the equation $$(xz+1)(yz+1)=P(z).$$

1. First we consider the case when $$x\mid a_3$$ or $$y\mid a_3$$. By symmetry, it suffices to deal with the case $$x\mid a_3$$. We fix $$x$$ for this section. By long division, we get an integral quadratic polynomial $$Q\in\mathbb{Z}[Z]$$ and a nonzero integer $$r\in\mathbb{Z}$$ such that $$a_3^2 P(Z)=(xZ+1)Q(Z)+r.$$ If $$xz+1\mid P(z)$$, then $$xz+1\mid r$$, hence there are finitely many possibilities for $$z$$ (and also for $$y$$).

2. Now we consider the case when $$x\nmid a_3$$ and $$y\nmid a_3$$. We rewrite the original equation as $$tz=x+y-a_1\qquad\text{where}\qquad t:=a_3z+a_2-xy.$$ Here $$t$$ is an integer. If $$t\leq 0$$, then $$x+y\leq a_1$$, which leads to finitely many triples $$(x,y,z)$$. So let us focus on the case $$t>0$$. We use an identity inspired by the OP's earlier post: \begin{align*} (tx-a_3)(ty-a_3)&=t^2 xy-a_3 t(x+y)+a_3^2\\ &=t^2(a_3z+a_2-t)-a_3 t(tz+a_1)+a_3^2\\ &=-t^3+a_2 t^2-a_1 a_3 t+a_3^2. \end{align*} We conclude that $$t\leq 3\max(|a_1|,|a_2|,|a_3|)$$, for otherwise the LHS is positive, while the RHS is negative. Moreover, the factors on the LHS are nonzero integers by $$x\nmid a_3$$ and $$y\nmid a_3$$. So there are finitely many possibilities for the factors on the LHS (namely they are integral divisors of the finitely many possible values of the RHS), hence also for the triple $$(x,y,z)$$.

• For the above result to have application in primality testing, we need to explicitly determine a value $z_{min}$ as function of $a_3, a_2, a_1$ so that for all $z >z_{min}$, $xz+1$ is not a proper divisor of $P(z)$. From the last inequality of Case 2 of your proof, all solutions $(x, y, z)$ have $z<a_3^2 +2a_3+a_2m^2 - a_1a_3-1$ where $m=3$max$(|a_1|,|a_2|,|a_3|$). However the upper bound of $z$ in Case 1 is not clear.
– ASP
May 6, 2021 at 12:40
• Currently I am researching on the question : Given a prime $p$ and a positive integer $a$, Is there an efficient way of determining whether $sp+1$ is a proper divisor of $ap+1$ or at least can we find some forms of integers $a$ such that it can be efficiently determined whether $sp+1$ is a proper divisor of $ap+1$. I have found a few such integers $a$, I'll share the idea in another post to see if the idea can be generalized.
– ASP
May 6, 2021 at 12:42
• @DavidJones: In Case 1, the nonzero integer $r$ can be explicitly determined as a polynomial of $(a_1,a_2,a_3,x)$ by running the division algorithm for $a_3^2 P(Z)$ and $xZ+1$. As $x$ is a divisor of $a_3$, we get an explicit upper bound for $r$ in terms of $(a_1,a_2,a_3)$, which is then an upper bound for $z$ as well. May 6, 2021 at 14:44