6
$\begingroup$

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<P(z)$. 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.

$\endgroup$
13
  • 1
    $\begingroup$ Why do you want to prove that and how do you know it's true? $\endgroup$ May 5, 2021 at 20:03
  • 1
    $\begingroup$ 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). $\endgroup$
    – LSpice
    May 5, 2021 at 20:26
  • 1
    $\begingroup$ 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 $\endgroup$
    – ASP
    May 5, 2021 at 20:28
  • 1
    $\begingroup$ 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 $\endgroup$
    – ASP
    May 5, 2021 at 20:31
  • 4
    $\begingroup$ 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. $\endgroup$ May 5, 2021 at 21:03

1 Answer 1

9
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – ASP
    May 6, 2021 at 12:40
  • $\begingroup$ 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. $\endgroup$
    – ASP
    May 6, 2021 at 12:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – GH from MO
    May 6, 2021 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.