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 ?