Euler's factorization method

<a href="/facts/Euler/z2fsbjgj">Euler</a>'s factorization method is a technique for <a href="/facts/Integer_factorization/EjMCTz2t">factoring</a> a number by writing it as a sum of two squares in two different ways. For example the number 
 
 
 
 1000009
 
 
 {\displaystyle 1000009}
 
 can be written as 
 
 
 
 
 1000
 
 2
 
 
 +
 
 3
 
 2
 
 
 
 
 {\displaystyle 1000^{2}+3^{2}}
 
 or as 
 
 
 
 
 972
 
 2
 
 
 +
 
 235
 
 2
 
 
 
 
 {\displaystyle 972^{2}+235^{2}}
 
 and Euler's method gives the factorization 
 
 
 
 1000009
 =
 293
 ⋅
 3413
 
 
 {\displaystyle 1000009=293\cdot 3413}
 
.
The idea that two distinct representations of an odd positive integer may lead to a factorization was apparently first proposed by <a href="/facts/Marin_Mersenne/Yklw7IGN">Marin Mersenne</a>. However, it was not put to use extensively until one hundred years later by Euler. His most celebrated use of the method that now bears his name was to factor the number 
 
 
 
 1000009
 
 
 {\displaystyle 1000009}
 
, which apparently was previously thought to be prime even though it is not a <a href="/facts/Pseudoprime/9kxvS7Y5">pseudoprime</a> by any major primality test.
Euler's factorization method is more effective than Fermat's for integers whose factors are not close together and potentially much more efficient than trial division if one can find representations of numbers as sums of two squares reasonably easily. The methods used to find representations of numbers as sums of two squares are essentially the same as with finding differences of squares in <a href="/facts/Fermat%2527s_factorization_method/XecvbCoo">Fermat's factorization method</a>.

Euler's factorization method open-in-new

Euler's factorization method