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 ?

  • $\begingroup$ 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$. $\endgroup$ – Ahmad Sep 25 '17 at 10:33
  • $\begingroup$ 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$. $\endgroup$ – Friedrich Sep 25 '17 at 10:43
  • $\begingroup$ jstor.org/stable/2323912?seq=1#page_scan_tab_contents $\endgroup$ – Will Jagy Sep 25 '17 at 17:59

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.