## Gaussian integers and Fermat’s Theorem

Lemma: The congruence $x^2\equiv -1\pmod{p}$ has a solution modulo a prime $p$ if and only if $p=2$ or $p\equiv 1\pmod{4}$.

Proof: If $p=2$, $1$ is a solution. If $p$ is odd, and $x^2=-1$ has a solution, then $(\Zn{p})^{\times}$ has an element of order $4$, so $4\divides (p-1)$. Notice that $(\Zn{p})^{\times}$ has only two elements of order dividing $2$, because of $x^2\equiv 1\pmod{p}$ then $p\divides (x^2-1)$, so $p\divides (x+1)(x-1)$, so either $x\equiv 1\pmod{p}$ or $x\equiv -1\pmod{p}$. If $4\divides (p-1)$ then let $H$ be the Sylow $2$-subgroup of $(\Zn{p})^{\times}$. If $H$ were not cyclic, then there would be too many elements of order $2$ in $H$. So $H$ must be cyclic and therefore there is an element of order $4$.

Now suppose that $p\equiv 1\pmod{4}$. Let $u$ be a solution to $x^2+1\equiv 0\pmod{p}$. Consider the ideal $I=(p,u+i)\subset \Z[i]$. This is a maximal ideal. If $\pi=a+bi$ is a generator of this ideal, then $p=x\pi$. If $x$ were a unit, then $u+i$ would have to be a multiple of $p$, which it visibly isn’t. Therefore $N(\pi)$ must be $p$.
But $N(\pi)=a^2+b^2$, so we’ve found our representation.

Proposition: The ring $\Z[\sqrt{-5}]$ is not a Euclidean ring. In fact, the ideal $(3,1+\sqrt{-5})$ is not principal. It is a proper ideal, because the quotient of $\Z[\sqrt{-5}]$ by this ideal is $\Zn{3}$. If $\pi$ were a generator of this ideal, then $3=x\pi$ means that either $N(\pi)=3$ or $N(\pi)=9$. Also $(1+5i)=y\pi$ means that $N(\pi)$ divides $6$. Since $\pi$ is not a unit, $N(\pi)=3$. But the equation $x^2+5y^2=3$ has no integer solutions, so there is no element of norm 3 in this ring.

## Principal Ideal domains

Definition: An integral domain in which every ideal is principal is called a Principal Ideal Domain.

Principal ideal domains satisfy the conclusions of the Euclidean algorithm (but maybe without the algorithm).

That is, given $a,b\in R$ if $R$ is a PID, then the ideal $(a,b)=(d)$ where $d$ is a greatest common divisor of $R$, and there are $x$ and $y$ in $R$ such that $ax+by=d$. The gcd $d$ is unique up to multiplication by a unit.

Proposition: A Euclidean ring is a PID. (DF p. 281 contains a strengthening of this result, proving that an integral domain $R$ is a PID if and only if it has a “Dedekind-Hasse” norm, which is a slightly more general type of norm that isn’t necessarily positive)

Note: The converse is not true, but the question of existence of Euclidean algorithms is subtle. See Conrad’s notes on the euclidean domains for a discussion. DF prove that $\Z[(1+\sqrt{-19})/2]$ is a PID but is not Euclidean with respect to any norm (see page 277).

Proposition: In a principal ideal domain, every nonzero prime ideal is maximal.