A generalization of Euler Factorization with $N = m a^2 + n b^2 = m c^2 + n d^2$

Question

In Euler Factorization, we try to represent a positive integer $N$ as the sum of two squares in two different ways i.e.,

$$ N = a^2 + b^2 = c^2 + d^2 $$

Let $$ \begin{align} a-c & = kl, \\ d-b & = km, \\ (l,m) & = 1, \\ a+c & = mn, \\ b+d & = ln \end{align} $$

then Euler gave the formula:

$$ N = \left[\left(\frac{1}{2} k\right)^2 + \left(\frac{1}{2} n\right)^2\right](l^2 + m^2) $$

John Brillhart discusses a generalization of this method in [JB2009] by representing $N$ in two different ways as $N = m a^2 + n b^2 = m c^2 + n d^2$ and provides a proof in Theorem 2 in the note, reproduced below:

Theorem 2 [JB2009]. Let $N > 1$ be an odd integer expressed in two different ways as

$$ N = m a^2 + n b^2 = m c^2 + n d^2, $$

where $a, b, c, d, m, n \in \mathbb{Z^{+}}, b < d$ and $(ma, nb) = (mc, nd) = 1.$ Then

$$ N = (N, ad - bc) \cdot \frac{N}{(N, ad - bc)}. $$

Proof omitted.

---

In an effort to find suitable $a, b, c, d, m, n$ for a given integer $N$, I am using the following procedure:

1. Choose $a, b$ such that $(a,b) = 1$.
2. Solve $$N = a^2 m + b^2 n \tag{1}$$ for $m, n$ using Extended Euclid's algorithm. This is the first representation of $N$.
3. If we fix $m, n$ and solve the equation $mX + nY = N$ then by the same Extended Euclid's algorithm, there are an infinite number of solutions for $X, Y$, provided $(m,n)=1$ (Note: If $(m,n) \ne 1$ then the $(m,n)|N$). We are looking for square solutions of the form

$$ \begin{align} X = c^2 & = a^2 - nt, \\ Y = d^2 & = b^2 + mt, \\ t & \in \mathbb{Z} \end{align} \tag{2} $$

4. If $t = 2a - n = 2b + m$ then

$$ \begin{align} c^2 & =a^2-n(2a-n)=a^2-2an+n^2=(a-n)^2, \\ d^2 & =b^2+m(2b+m)=b^2+2bm+m^2=(b+m)^2. \end{align} \tag{3} $$

$$ \therefore m+n = 2a - 2b \tag{4} $$

is a sufficient condition for square solutions to exist.

5. Suppose $m_0, n_0$ is a solution to Eqn. $(1)$. Then

$$ \begin{align} m & = m_0 - b^2 u, \\ n & = n_0 + a^2 u, \\ u & \in \mathbb{Z} \end{align} \tag{5} $$

6. Therefore,

$$ \begin{align} m+n & =m_0+n_0+a^2 u-b^2 u \\ \implies 2(a-b) & =m_0+n_0+(a^2-b^2 )u \\ \implies (a-b)(2-(a+b)u) & =m_0+n_0 \end{align} \tag{6} $$

7. Solve for $u$ in Eqn. $(6)$ and substitute in Eqn. $(5)$ to get $m, n$.

8. Substitute $m, n$ in Eqn. $(3)$ to get $c, d$.

9. Factorize $$N = (N, ad - bc) \cdot \frac{N}{(N, ad - bc)}.$$

The effectiveness of this procedure hinges on the choice of $a, b$ such that in Step 6. we can find an integer solution for $u$ by solving

$$ (a-b)(2-(a+b)u) = m_0+n_0 \tag{7} $$

Question:

1. How does one effectively choose $a,b$ so that Eqn. $(7)$ can be solved in integers for $u$?

One idea is to choose $a,b$ to be consecutive integers so that $a - b = 1$ and $(a,b)=(a,a-1)=1$ which ensures $m_0, n_0$ exists and then Eqn. $(7)$ becomes

$$ \begin{align} m_0+n_0 & = (a-b)(2-(a+b)u) \\ & = 1 \cdot (2-(a+b)u) \\ & = 2-(a+a-1)u \\ \implies (2a-1)u & = 2 - m_0 - n_0 \\ \implies u & = \frac{2 - m_0 - n_0}{2a-1} \end{align} $$

So, this now reduces to choosing suitable $a$ such that $2a-1$ divides $2 - m_0 - n_0$.

2. In step 3, what is the guarantee that there exist square solutions for Eqn. $(2)$

---

An update (Jul 7, 2023):

Let $K$ be a rational number such that

$$ \begin{align} N&=ma^2+nb^2=m(K-a)^2+n(K-b)^2 \\ &=m(K^2-2Ka+a^2 )+n(K^2-2Kb+b^2 ) \\ &=K^2 (m+n)-2K(am+bn)+(ma^2+nb^2 ) \\ &=K^2 (m+n)-2K(am+bn)+N \end{align} $$ Therefore $$ K^2 (m+n)=2K(am+bn) \\ K=2\left(\frac{am+bn}{m+n}\right) $$

i.e., if $(m+n) | 2(am+bn)$ then $K$ is an integer then we may have the two required representations of $N$.

So, factoring $N$ may be reduced to finding $a, b, m, n$ such that $(m+n) | 2(am+bn)$.

Also, suppose the two representations are unique. Then, by Brillhart, a non-trivial divisor can be found using $(N, ad - bc)$.

i.e.,

$$ \begin{align} ad - bc & = a(K-b) - b(K-a) \\ & = aK - ab - bK + ab \\ & = (a-b)K \end{align} $$

So, the non-trivial divisor is $(ad - bc, N) = ((a-b)K, N)$.

The question still remains. How do we choose $a, b, m, n$?

---

An update (Jul 11, 2023):

The method in [HMW1990] gives an algorithm for solving $n = fu^2 + g\upsilon^2$ in coprime integers $u$ and $\upsilon$.

It has running time $O\left(n^{\frac{1}{4}} (\log n)^3 (\log \log n) (\log \log \log n)\right)$.

We could use this algorithm to find $N = ma^2 + nb^2 = mc^2 + nd^2$ and then apply the Brillhart theorem to compute a non-trivial factor with a simple GCD.

---

References

[JB2009]: Brillhart, J. (2009). A Note on Euler’s Factoring Problem. The American Mathematical Monthly, 116(10), 928–931. http://www.jstor.org/stable/40391253

[HMW1990]: Hardy, K., Muskat, J. B., & Williams, K. S. (1990). A Deterministic Algorithm for Solving $n = fu^2 + g\upsilon^2$ in Coprime Integers $u$ and $\upsilon$. Mathematics of Computation, 55(191), 327–343. https://doi.org/10.2307/2008809

Answer 1

Is there an effective procedure for finding $a,b,c,d,m,n\in \mathbb Z^+$ such that we can apply the factorization method of Brillhart given in the reference?

If I understand your question correctly, the following should help.

Let us start with $$m a^2 + n b^2 = m c^2 + n d^2\tag1$$

$(1)$ can be written as $$m(a-c)(a+c)=n(d-b)(d+b)\tag2$$

Now, there are integers $k,p,q$ such that $$a-c=pk,\qquad d-b=qk,\qquad (p,q)=1$$

So, from $(2)$, we have $$mps=nqt$$ where $a+c=s$ and $d+b=t$.

So, under the condition that $(m,n)=1$, there is an integer $r$ such that $$ps=rn,\qquad qt=rm$$ where $r=(ps,qt)$ and $$m=\frac{qt}{(ps,qt)},\qquad n=\frac{ps}{(ps,qt)}$$

Therefore, we finally get $$a=\frac{pk+s}{2},\qquad b=\frac{t-qk}{2},\qquad c=\frac{s-pk}{2},\qquad d=\frac{t+qk}{2}$$ $$m=\frac{qt}{(ps,qt)},\qquad n=\frac{ps}{(ps,qt)}$$

and $$\begin{align}N&=ma^2+nb^2 \\\\&=\frac{qt}{(ps,qt)}\bigg(\frac{pk+s}{2}\bigg)^2+\frac{ps}{(ps,qt)}\bigg(\frac{t-qk}{2}\bigg)^2 \\\\&=\frac{qt(p^2k^2+2pks+s^2)+ps(t^2-2tqk+q^2k^2)}{4(ps,qt)} \\\\&=\frac{st(sq+tp)+k^2pq(sq+tp)}{4(ps,qt)} \\\\&=\frac{(st+k^2pq)(sq+tp)}{4(ps,qt)}\end{align}$$