$p=a^2+b^2,$ $p\equiv 1\pmod 4$, solve for $(a,b)$ [duplicate]
Let $p\equiv 1\pmod 4$ be prime. Then $p$ splits in $\mathbb{Z}[i]$ into non-units $(a+ib)(a-ib)=p$. Thus it is clear that $p=a^2+b^2$.
Question: How does one determine $(a,b)$?
According to Dedekind-Kummer (the extension is monogenic) and with $\mathfrak{p}=(p)$ in $\mathbb{Z}$, we have that $\mathfrak{p}\mathbb{Z}[i]=(p,\zeta_4-x)(p,\zeta_4-y)$, where $\zeta_4$ is a primitive $4$-th root of unity, and $x,y$ are the two primitive $4$-th roots of unity modulo $p$.
But $\mathbb{Z}[i]$ is a PID, so can write these ideals with a principal element, which should be $a+ib$ and $a-ib$. How can one do this?
-
Find integer $x>0$ such that $p$ divides $x^2+1$.
-
Find $u,v$ between $1$ and $\lfloor \sqrt{p}\rfloor$ with $xu\equiv \pm v\pmod{p}$.
-
Then $x^2+1\equiv 0\pmod{p}$ implies $x^2u^2+u^2\equiv v^2+u^2\equiv 0\pmod{p}$.
-
But $v^2+u^2<2p$, so $v^2+u^2=p$.