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 $?



Finding all proper divisors of $a_3z^3 +a_2z^2 +a_1z+1$ of the form $xz+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](https://en.wikipedia.org/wiki/Integer_factorization).


