Finding all proper divisors of $a_3z^3 +a_2z^2 +a_1z+1$ of the form $xz+1$

Question

Let $n=a_3z^3+a_2z^2+a_1z+1$ where $a_1<z, \ a_2<z, \ 1 \le a_3<z, z>1$ are non negative integers. To obtain proper divisors of $n$ of the form $xz+1$, one may perform trial divisions $xz+1 \ | \ n$, for all $xz+1 \le \sqrt n$. Trial division however is inefficient as $z$ becomes large. The method below is much more efficient. Since $xz+1 \ | \ n$ , we may write $(xz+1)(yz+1)=n$. Assume $y \le x$. We consider two cases;

**Case 1: ** $1 \le x <z$ and $1 \le y<z$

$xyz+x+y=a_3z^2+a_2z+a_1$. Since every positive integer has a unique base $z$ representation we have; \begin{equation} x+y=C\cdot z+a_1 , C=0 \ \text{or} \ 1 \ \end{equation} \begin{equation} xy+C = a_3z+a_2 \end{equation} Solving the two equations for the cases $C=0$ and $C=1$, $x$ and $y$ can be determined.

**Case 2: ** $z\le x<z^2$ and $1 \le y<z$

Let $x=x_1z+x_0$ and $y = y_0$, $1\le x_1<z, \ 0 \le x_0<z$, $ 1 \le y_0 <z$. So \begin{equation} x_1y_0z^2+(x_0y_0+x_1)z+x_0+y_0=a_3z^2+a_2z+a_1 \end{equation} Comparing coefficients of powers of $z$; \begin{equation} x_0+y_0=C_1 \cdot z+a_1, \ C_1 = 0 \ \text{or} \ 1 \end{equation} \begin{equation} x_0y_0+x_1+C_1=C_2 \cdot z+a_2 \end{equation} \begin{equation} x_1y_0+C_2=a_3 \end{equation} From the last equation, either $y_0 \le \sqrt a_3$ or $x_1 \le \sqrt a_3$. So we do trial divisions $yz+1 \ | \ n$ for all $y = y_0 \le \sqrt a_3$. Also for each value of $x_1 \le \sqrt a_3 $, we solve the three equations simultaneously to find $x_0, y_0$ and $C_2$ when $C_1=0$ and $C_1 = 1$.

Cases 1 and 2 exhaust all the possible cases.

In this example, we had $n < z^4$. How can this method be modified to efficiently find all proper divisors of the form $xz+1$ of an arbitrary positive integer $n$, $n \equiv \ 1 ($ mod $ z) $ or at least when $n<z^5 $?

Answer 1

Such an extension is highly unlikely to exist. Already in the simple case of $z=2$, it's equivalent to just factoring a given odd integer $n$, which is a famous hard problem.

Answer 2

An extension to the case when $n<z^5$ with some restrictions on $x$ and $y$:

Let $n=a_4z^4+a_3z^3+a_2z^2+a_1z+1$, $a_i < z $, $a_4>0, z>1$. We are looking for positive integes $x$ and $y$ such that $(xz+1)(yz+1)=n$. We add a restriction on $x$ and $y$; If $x=x_k \cdot z^k + \cdots + x_0$ and $y=y_t \cdot z^t + \cdots + y_0$ are the base $z$ represenations of $x$ and $y$, then $x_i \le x_k$ for all $i<k$ and $y_i \le y_t$ for all $i<t$.
Case 1: $x=x_1\cdot z+x_0$ and $y=y_0$
We get \begin{equation} x_1y_0z^3+(x_0y_0+x_1)z^2+(x_0+y_0)z+1=a_4z^4+a_3z^3+a_2z^2+a_1z+1 \end{equation} Comparing coefficients of powers of $z$;
\begin{equation} x_0+y_0=C_1\cdot z+a_1 , C_1=0 \ \text{or} \ 1 \end{equation} \begin{equation} x_0y_0+x_1+C_1=C_2\cdot z+a_2 \end{equation} \begin{equation} x_1y_0+C_2=a_4\cdot z+a_3 \end{equation} From the last equation, $x_1y_0 < (a_4+1) \cdot z$ and since it's assumed that $x_0 \le x_1$, we have $x_0y_0+x_1+C_1<(a_4+2)\cdot z$ , therefore $C_2 \le a_4+1$. By solving the three equations for $C_2=0, 1, \cdots , a_4+1$, all solutions with $x_0 \le x_1$ are found.

Case 2: $x=x_1\cdot z+x_0$ and $y=y_1\cdot z+y_0$
We get $x_1y_1z^4 + (x_0y_1 + x_1y_0)z^3 + (x_0y_0+x_1+y_1)z^2+(x_0+y_0)z+1=a_4z^4+a_3z^3+a_2z^2+a_1z+1$
Comparing coefficients of powers of $z$;
\begin{equation} x_0+y_0=C_1\cdot z +a_1 \ \ C_1 = 0 \ \text{or} \ 1 \end{equation} \begin{equation} x_0y_0+x_1+y_1+C_1=C_2\cdot z +a_2 \end{equation} \begin{equation} x_0y_1+x_1y_0+C_2=C_3\cdot z +a_3 \end{equation} \begin{equation} x_1y_1+C_3=a_4 \end{equation} From the last equation, we have $x_1y_1 \le a_4 < z$. Assuming $x_0 \le x_1$ and $y_0 \le y_1$ we have, \begin{equation} x_0y_0+x_1+y_1+C_1 < 3z \end{equation} Therefore $C_2 \le 2$. And from the second last equation we have, \begin{equation} x_0y_1+x_1y_0+C_2 \le 2z \end{equation} Therefore $C_3 \le 2$.
Solving the four equations for all the 18 combinations of $C_1 \le 1$, $C_2 \le 2$, $C_3 \le 2$, all solutions $x_1,x_0,y_1,y_0$ are found.

The last case when $x$ and $y$ have $3$ base $z$ digits and $1$ base $z$ digits respectively can be tackled in the same way.