6
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ 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).$ $\endgroup$ Apr 25, 2021 at 21:53

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .