Euler's factorization method is a technique for factoring 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 10002+32{\displaystyle 1000^{2}+3^{2}} or as 9722+2352{\displaystyle 972^{2}+235^{2}} and Euler's method gives the factorization 1000009=293⋅3413{\displaystyle 1000009=293\cdot 3413}.
