# 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?

• Yes, this is fine. You get a smaller pair (in some sense) by replacing $1$ with $-1$ in your final formula. Then you get $(x,y)=11(36,31)$ rather than $(x,y)=11(24,41).$ Apr 25, 2021 at 21:53

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.$$

Especial case:

Due to Fermat theorem $$N=4k+1=m^2+n^2$$ and we have:

$$4k+1\equiv 1 \bmod 3\Rightarrow k\equiv 0\bmod 3$$

Therefore parametric form of N can be:

$$N=12 t+1$$

So we can first check whether N can be written as the sum of two primes or not. For example $$273097=22758\times 12+1$$, so it is among the numbers of this type. To find numbers m and m we may use following identity:

$$(2k+1)+(2i^2-k+1)^2=(2i^2-k)^2+(2i)^2\space\space\space\space\space\space$$ (1)

$$LHS= 4i^4+4i^2(1-k)+k^2=N\space\space\space\space\space\space\space\space\space$$ (2)

So i and k must be divisible by some prime factors of N. Also the solution of problem leads to solving Diophantine equation (2). For example:

$$4i^4+4i^2(1-k)+k^2=273097$$

gives $$(k, i)=(34397, 132), (35299, 132),(78067, 198), (78749, 198)$$

and we have:

$$273097=(2i^2-k)^2+(2i)^2=(451^2+264^2), (-451^2+264^2), (-341^2+396^2),(341^2+396^2)$$

This method may be suitable for large numbers.