1
$\begingroup$

The algorithm is based on the following observation. An integer $b>a$ can be written as $b=a + k$ with a and k integers. So if we want to find a sum of 2 squares of an integer N, we start by writing $N= a^2 + b^2$. Then we transform this equation into a useful one by rewriting it as $$N= a^2 + b^2= a^2 + (a+k)^2$$ This equation is just a quadratic in $a$. Namely $$2a^2 +2ak +k^2-N=0$$ Its discriminant is given by $$d=2N-k^2=s^2$$ Basically, we want to find the values of k that make the discriminant d a square. The fact that there is a minus sign before $k^2$ guarantees that the number of steps to find a solution is finite.

Let's take the example of $N=41$ to see how the method works in practice. We are looking for values of $k$ that make $d=82-k^2$ a square. We can see that $k=1$, the first value of $k$ makes $d$ a square with $d=9^2$. And this value of $d$ in turn provides us with two values of $a$, $a=2$ and $a=-5$.

Do we need to check every single value of $k$ to see if it makes $d$ a square? The answer is no. 82 is of the form $4m+2$ and squares are known to be of the form $4m+1$ or $4m$. We can rewrite $82-k^2=s^2$ as $82=k^2+s^2$ and the only possible combinations of last digits of the squares $k$ and $s$ that can add up to 2 in 82 are $(6,6)$ and $(1,1)$. However the $(6,6)$ can be dropped because squares that have a last digit of 6 are of the form $4m$ and therefore will not produce the 2 in 82. So that leaves only the $(1,1)$ combination of last digit of $k$ and $s$.

We see that this method does not require the factors of N when N is a composite number. We also see that it is probably the simplest method and the easiest to understand. The information on which integers can be put into the form $N=a^2 + b^2$ is known and can be found elsewhere (wikipedia).

Is this method the simplest?

$\endgroup$
  • 2
    $\begingroup$ You basically transformed the question how is $N$ representable in the form of the sum of two squares $a^2+b^2$ into a question how is $2N$ representable as a sum $k^2+s^2$. That doesn't seem easier. $\endgroup$ – Wolfram Jan 28 '17 at 22:13
  • $\begingroup$ sure, but how much complexity is added when we switch from N to 2N. It's just a consequence of using a quadratic equation, which even a high school student can understand. $\endgroup$ – user25406 Jan 28 '17 at 22:20
  • $\begingroup$ I agree with @Wolfram, everything you write after "Basically" can be used without the first steps, so those add only unuseful complexity. $\endgroup$ – N74 Jan 28 '17 at 22:31
  • $\begingroup$ @user25406 They are asymptotically equivalent with complexity $O(\sqrt{N})$, and the constants highly depend on luck. What are you trying to do exactly? $\endgroup$ – Wolfram Jan 28 '17 at 22:38
  • $\begingroup$ @Wolfram, when I mention "simplicity of use", I have in mind the math involved, not the complexity as such. I don't know enough to say anything about the complexity of any sum of 2 squares methods. But if I understand, you are saying they are basically equivalent in terms of complexity. Can you please clarify what you mean by "constants highly depend on luck". thanks. $\endgroup$ – user25406 Jan 29 '17 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.