<s>[INST] Sums of Squares algorithm I want to express a large number as the sum of two squares, given that it is possible and given its prime factors.  Let's say the number is $273097$.  It's prime factors are $11^2, 37$ and $61$.  Here is is easy to see $11^2=11^2+0^2$ and $37=6^2+1^2$. Through trial and error I found that $61=5^2+6^2$, but having read Efficiently finding two squares which sum to a prime, it looks like I just needed to notice that $11^2\equiv-1\pmod{61}$ and I could then apply the Euclidean algorithm to $61$ and $11$ to find the first two remainders below $\sqrt{61}$, which are of course $5$ and $6$.  Then I have $273097=11^2(6\times5-1\times6)^2+11^2(6\times6+1\times5)^2$. Is this the best way going about a question like this?
 [/INST] Prime number $p$ can be expressed as sum of two (non-zero) squares if $p\equiv 1 \pmod{4}$.
We know $37 = 1^2 + 6^2, 61 = 5^2 + 6^2.$
Hence $37$ and $61$ are expressed using Gaussian integers below.
Norm$(1+6i) = (1+6i)(1-6i) = 1^2 + 6^2 = 37$
Norm$(5+6i) = (5+6i)(5-6i) = 5^2 + 6^2 = 61$
Since $273097 = 11^2\cdot37\cdot61$ = Norm$(11(1\pm6i)(5\pm6i))$, then we get
$11(1+6i)(5+6i) = -341+396i  \implies 273097 = 341^2 + 396^2.$
$11(1-6i)(5+6i) = 451-264i   \implies 273097 = 451^2 + 264^2.$
$11(1+6i)(5-6i) = 451+264i   \implies 273097 = 451^2 + 264^2.$
$11(1-6i)(5-6i) = -341-396i  \implies 273097 = 341^2 + 396^2.$
</s>