Euler's factorization method

The Brahmagupta–Fibonacci identity states that the product of two sums of two squares is a sum of two squares. Euler's method relies on this theorem but it can be viewed as the converse, given ${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$ we find ${\displaystyle n}$ as a product of sums of two squares.

First deduce that

${\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}$

and factor both sides to get

${\displaystyle (a-c)(a+c)=(d-b)(d+b)}$ (1)

Now let ${\displaystyle k=\operatorname {gcd} (a-c,d-b)}$ and ${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$ so that there exists some constants ${\displaystyle l,m,l',m'}$ satisfying

• ${\displaystyle (a-c)=kl}$,
• ${\displaystyle (d-b)=km}$,

${\displaystyle \operatorname {gcd} (l,m)=1}$

• ${\displaystyle (a+c)=hm'}$,
• ${\displaystyle (d+b)=hl'}$,

${\displaystyle \operatorname {gcd} (l',m')=1}$

Substituting these into equation (1) gives

${\displaystyle klhm'=kmhl'}$

Canceling common factors yields

${\displaystyle lm'=l'm}$

Now using the fact that ${\displaystyle (l,m)}$ and ${\displaystyle \left(l',m'\right)}$ are pairs of relatively prime numbers, we find that

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

So

• ${\displaystyle (a-c)=kl}$
• ${\displaystyle (d-b)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

We now see that ${\displaystyle m=\operatorname {gcd} (a+c,d-b)}$ and ${\displaystyle l=\operatorname {gcd} (a-c,d+b)}$

Applying the Brahmagupta–Fibonacci identity we get

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(a-c)+(a+c){\bigr )}^{2}+{\bigl (}(d-b)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.}$

As each factor is a sum of two squares, one of these must contain both even numbers: either ${\displaystyle (k,h)}$ or ${\displaystyle (l,m)}$. Without loss of generality, assume that pair ${\displaystyle (k,h)}$ is even. The factorization then becomes

${\displaystyle n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,}$

Since: ${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

we have from the formula above:

Thus,

${\displaystyle 1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\right)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,}$

${\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,}$

${\displaystyle =(4+289)\cdot (49+3364)\,}$

${\displaystyle =293\cdot 3413\,}$

• Ore, Oystein (1988). "Euler's Factorization Method". Number Theory and Its History. pp. 59–64. ISBN 978-0-486-65620-5.
• McKee, James (1996). "Turning Euler's Factoring Method into a Factoring Algorithm". Bulletin of the London Mathematical Society. 4 (28): 351–355. doi:10.1112/blms/28.4.351.