Summe von Quadraten/Bestimmungsverfahren mit Gaußschen Zahlen/Verfahren

Es sei ${}p$ eine Primzahl, die modulo ${}4$ den Rest ${}1$ besitzt, so dass es nach Fakt eine Darstellung als Summe von zwei Quadraten geben muss. Wie findet man eine solche Darstellung explizit? Einerseits durch probieren, andererseits kann man aber entlang dem Beweis des Satzes vorgehen. Dazu muss man folgende Schritte gehen:

1. Finde in ${}\mathbb {Z} /(p)$ ein Element ${}a$ mit ${}a^{2}=-1$. Um dies zu finden braucht man in der Regel ein primitives Element in diesem Restklassenkörper (ist ${}b$ ein primitives Element, so kann man ${}a=b^{(p-1)/4}$ nehmen; siehe auch Aufgabe).
2. Die Abbildung ${}\mathbb {Z} [{\mathrm {i} }]\rightarrow \mathbb {Z} /(p)$, die ganze Zahlen modulo ${}p$ nimmt und ${}{\mathrm {i} }$ auf ${}a$ schickt, ist ein surjektiver Ringhomomorphismus auf einen Körper. Der Kern ist ein Hauptideal, das von ${}p$ und von ${}a-{\mathrm {i} }$ erzeugt wird.
3. Finde mit dem euklidischen Algorithmus einen Erzeuger ${}z$ für das Hauptideal ${}(p,a-{\mathrm {i} })$. Ein solcher Erzeuger hat die Norm ${}N(z)=p$. Eine Zerlegung ${}p=zw$ führt ja generell auf ${}N(z)N(w)=N(p)=p^{2}$.