# Proof algorithm to find representations as sum of two squares

I saw in a book the following algorithm to find, given a prime $p\equiv 1 \pmod 4$, integers $a$ and $b$ such that $p=a^2+b^2$.

Step 1 : Find an integer $0 <m <p$ such that $m^2\equiv -1\pmod p$ (there is a clever method to do it but that's not the question here)

Step 2 : Run the Euclidean algorithm with $p$ and $m$. Then the two first remainders which are less than $\sqrt p$ satisfy $r_1^2+r_2^2=p$.

I can't prove that the algorithm indeed works. I see that it suffices to prove that $r_1^2+r_2^2$ is divisible by $p$ but I don't see how to do it. Can you give me a hint ?

• As for the first step you need to $a=2$ and do $a^{\frac{p-1}{2}} = -1 \mod p$ then $m = a^{\frac{p-1}{4}} \mod p$. – Ahmad Sep 25 '17 at 10:33
• I know how to do the first step. And you are wrong, $2^{\frac {p-1}{2 }}$ is not always $-1$ modulo $p$... It depends on $p \mod 8$. – Friedrich Sep 25 '17 at 10:43
• jstor.org/stable/2323912?seq=1#page_scan_tab_contents – Will Jagy Sep 25 '17 at 17:59