The Euclidean Algorithm and Integer Factoring

Question

Theorem 1. Let $N=pq+rs$ where $p=q+r+s$. Then $N=(q+r)(q+s)$.

Proof. Let $N = pq + rs$ and $p = q+r+s$.

Then,

$$ \begin{align} N & = (q+r+s)q + rs \newline & = q(q+r) + s(q+r) \newline & = (q+r)(q+s). \end{align} $$

$\blacksquare$

Consider the Linear Diophantine equation

$$ N = ax + by \tag{1} $$

with $(a,b) = 1$. This equation has an infinite number of solutions for $x, y \in \mathbb{Z}$.

Using the Extended Euclidean Algorithm, we can find a particular solution $x_0, y_0$. The general solution is given by

$$ \begin{align} x & = x_0 - bt, \newline y & = y_0 + at, \newline t &\in \mathbb{Z} \end{align} \tag{2} $$

If $a = x + b + y$ then, by Theorem 1, we have $$N = (x + b)(x + y) \tag{3}$$

We have $$a = x_0 - bt + b + y_0 + at \tag{4}$$. i.e.,

$$ t = 1 + \frac{x_0 + y_0}{b-a} \tag{5} $$

We want $t$ to be an integer and $t$ is an integer iff $(b-a) | (x_0 + y_0)$.

Substituting, Eqns. $(2)$ and $(5)$ in Eqn. $(3)$, we have

$$ \begin{align} N & = (x + b)(x + y) \newline & = (x_0 - bt + b)(x_0 - bt + y_0 + at) \newline & = (x_0 - b(t - 1))(x_0 + y_0 - t(b-a)) \end{align} \tag{6} $$

Observations:

1. We are trying to use this method to factor $N$. So, let us assume that the factors of $N$ are unknown. An obvious choice is $b = a+1$ that satisfies $(a,b) = (a,a+1) = 1$ and we have $t = 1 + x_0 + y_0 \in \mathbb{Z}$. But, when we substitute this in Eqn. $(6)$, we get

$$ \begin{align} N & = (x_0 -b(x_0 + y_0))(x_0 + y_0 -(x_0 + y_0 + 1)(b-a)) \newline & = (x_0 - b(x_0 + y_0))(-1) \newline \end{align} $$

2. This only gives us trivial factors $-N, -1$ when we take $b = a+1$.

3. This means $b-a \ne 1$, if we are looking for non-trivial factors of $N$.

4. Also, we cannot find $x_0', y_0'$ and then hope to find $x_0 = x_0' - bm, y_0 = y_0' + am$ for some integer $m$ because that still leads to $(b-a)|(x_0' + y_0')$.

Question:

Is there a way we can choose $a,b$ such that $(b-a)|(x_0 + y_0)$ and thereby we obtain the factors of $N$?

One way we could do that is to fix $a$ and then take successive values $b \gt a$ satisfying $(a,b) = 1$ and compute $x_0, y_0$ using the Extended Euclidean algorithm and stopping when the condition $(b-a)|(x_0 + y_0)$ is met. For eg: if $a = 1$, we choose successive integers $b \gt 1$ and try.

Is there a better way?