Efficicient algorithm to check if $az+1=(xz+1)(yz+1)$

Question

Given two positive integers $a$ and $z$ with $z$ prime, consider the problem of determining whether the integer $az+1$ can be factored as $az+1=(xz+1)(yz+1)$, where $x, y$ are positive integers and $xz+1$ is prime. This problem can be solved by checking if $yz+1 \ | \ az+1$ for some integer $y$, $yz+1 \le \sqrt{az+1}$.

Trial division however is too slow when $a/z$ is large. Is there an efficient algorithm for solving this problem or a particular case. (Note that we are not interested in finding factors of $az+1$, only to determine if it can be factored this way).

A related but different question is here Prove that the diophantine equation $(xz+1)(yz+1)=az^{3} +1$ has no solutions in positive integers $x, y, z$ with $z>a^{2} +2a$.

Answer 1

I'll give a heuristic argument for the following claim: any algorithm that solves this problem cannot be faster than factoring $az+1$.

From there it is well known what the asymptotic complexity is, plus what algorithms are actually faster when implemented in a programming language and so on.

Consider the first few cases with small $z$:

$z=2$

The algorithm returns true if and only if $az+1$ is composite. I proved this a couple days ago here.

$z=3$

Let the factorization of $az+1$ be the following:

$$az+1=\prod_i p_i^{a_i}\prod_i q_i^{b_i}$$

Where $p_i\equiv 1 \mod 3$ and $q_i\equiv 2 \mod 3$. We have that $\sum b_i \equiv 0 \mod 2$ since $az+1\equiv 1 \mod 3$. The factorization is impossible again if $az+1$ is prime but also in the case where $\sum b_i = 2$ and there are no $a_i$ i.e. when it is the product of two primes $\equiv 2 \mod 3$. It's easy to see that all other cases allow you to group the primes into two factors that are $\equiv 1 \mod 3$, all of which get you a valid factorization.

The case $z=4$ is very similar to the previous one. But when $\varphi(z)$ starts getting larger it gets more complicated. The case $z=5$ is as follows:

Let

$$az+1=\prod_i p_i^{a_i}\prod_i q_i^{b_i}\prod_i r_i^{c_i}\prod_i s_i^{d_i}$$

Where the classes of prime numbers are those congruent to $1,2,3,4$ mod 5 respectively. Let also $A=\sum_i a_i$ and the same for the other three residue classes. Then $az+1$ is of the form $(5x+1)(5y+1)$ when all of the following are false:

• It is prime;

• $A=C=D=0$ and $B=4$;

• $A=D=0$ and $B=C=1$;

• $A=C=0$ and $B=2$ and $D=1$;

As you can see, these are increasingly complicated statements about the prime factorizations of $az+1$. So I don't think your question can be answered faster than actually factoring it.

Answer 2

As GerryMyerson writes, "$az+1=(xz+1)(yz+1)=xyz^2+xz+yz+1,\ a=xyz+x+y,$ so a restatement of the question is whether, given $a,z,$ there is an efficient way to decide whether there exist $x,y$ such that $a=xyz+x+y.$"

Then, a restatement of this is whether, given $a,z$ and $a=qz+r,$ there exist $x,y$ such that $xy=q$ and $x+y=r.$ But this corresponds to solving $x(r-x)=q$ which has solutions $$ 2x = r \pm \sqrt{r^2-4q}. $$ Thus, we need to decide whether $r^2-4q$ is a square number, say $s^2.$

Now, $r^2-4q=s^2$ is equivalent to $(r+s)(r-s)=4q$ which means that we need to find all factorizations of $4q.$

Answer 3

Taking in account GerryMyerson comment, easily to get the system in the form of \begin{cases} az+1=(xz+1)(yz+1) = 1+ z(x+y) + z^2xy\\ a=xyz+x+y=(xz+1)y+x=(yz+1)x+y\\ x\le y\\ a,x,y,z\in\mathbb N,\tag1 \end{cases} where $\;x,y\;$ are unknowns and $\;a,z\;$ are parameters.

Denote $\;s=x+y,\;$ then $$4(az+1) = 4+4zs+z^2s^2-z^2s^2+4z^2x(s-x) =(zs+2)^2-z^2(s-2x)^2,$$ $$4(a-s) = z(s^2-(s-2x)^2),$$ $$a = zx(s-x)+s,$$ \begin{cases} y=s-x\\[4pt] s\in\left\{z\left\lfloor\dfrac{2\sqrt{1+az}-2}{z^2}\right\rfloor+(k-1)z+(a \mod z),\; k\in\mathbb N\right\}\cap\{1,2\dots a\}\\[4pt] 2x=s-\sqrt{s^2-\dfrac{4a-4s}z}.\tag2 \end{cases}

Therefore, the integer variable $\;s\;$ should change the values with the step $\;z.\;$

If $\;z\;$ is too small, then can be used analysis on the unused simple residue classes.

For example, the parity anlysis of $(1)$ gives the next additional constraints.

• If $\;\mathbf{(2\!\not|\;z)\wedge(2\!\not|\;a)},\;$ then $\;(2\,|\;az+1),\;(2\!\not|\;x)\vee(2\!\not|\;y).\;$
• If $\;\mathbf{(2\!\not|\;z)\wedge(2\,|\;a)},\;$ then $\;(2\!\not|\;az+1),\;(2\,|\;x)\wedge(2\,|\;y).\;$
• If $\;\mathbf{(2\,|\;z)\wedge(2\!\not|\;a)},\;$ then $\;(2\!\not|\;az+1),\;(2\,|\;x+y).\;$
• If $\;\mathbf{(2\,|\;z)\wedge(2\,|\;a)},\;$ then $\;(2\!\not|\;az+1),\;(2\!\,\not|\;x+y).\;$

Similar schemes allow to improve the computational complexity of the algorithm.

However, there are not a good simple algorithm for big numbers.