An odd prime $p$ can be expressed as $x^2 + y^2$ for integers $x$ and $y$ if and only if $p \equiv 1$ (mod 4).

Proof: It is easy to see that any number congruent to 3 (mod 4) cannot be expressed as the sum of two integer squares.

Now we want to show that every prime congruent to 1 (mod 4) can be written as $x^2 + y^2$ for $x,y \in \mathbb{Z}$.
Let $p$ be an odd prime congruent to 1 (mod 4). Suppose that $x$ and $y$ are positive integers such that $0<x,y< \sqrt{p}$. Then $0<x^2+y^2<2p$ so since there are no multiples of $p$ between $0$ and $2p$ besides $p$ itself, then $p \mid x^2 + y^2$ implies $p = x^2 + y^2$, as desired. Now we will show that there exist such $x$ and $y$.

Lemma: Let $n = \lfloor \sqrt{p} \rfloor$. Then for all $a \in \mathbb{U}_p$ there exist $x,y \in \{1,2,\dots,n\}$ such that $ax \equiv \pm y \pmod p$.

Proof of lemma: Let $r_1, r_2, \dots, r_n$ be the representatives of the multiples of $a$ modulo $p$. More precisely, $r_i$ is the unique element of $\{1,2,\dots,p-1\}$ that is congurent to $a\cdot i \pmod p$. Note that no two $r_i$ and $r_j$ are equal for distinct $i$ and $j$. Now suppose for the sake of contradiction that the lemma is false; that is for all $i$ between 1 and $n$, $n+1 \le r_i \le p-n-1$.

Let $s_1, s_2, \dots s_n$ be a reordering from least to greatest of $r_1, r_2, \dots, r_n$ so that for all $k$ from 1 to $n$, $s_k = r_i$ for some $i$, and $s_1<s_2<\dots <s_n$. Let $d = s_n - s_1$ be the distance between the greatest and least representatives. We will set upper and lower bounds on $d$ and show that both cannot be satisfied.

Since all $r_i$ are between $n+1$ and $p-n-1$ then $s_n - s_1 \le~(p-n-1)-(n+1)$ so $d\le p-2n-2$. Since $n>\sqrt{p}-1$ then $$d<p-2\sqrt{p}.$$

Now observe that $\lvert r_i - r_j \rvert = r_{\lvert i-j \rvert}$. Therefore since all representatives are at least $n+1$ apart then the positive difference between any two representatives must also be at least $n+1$. This means $s_2 - s_1 \geq n+1$, $s_3-s_2 \geq n+1, \dots, s_n-s_{n-1} \geq n+1$. Adding these $(n-1)$ inequalties together, $s_n-s_1 \geq (n+1)(n-1)$, or $d \geq n^2-1$. Since $n>\sqrt{p}-1$ then $n^2>p-2\sqrt{p}+1$, or $n^2-1>p-2\sqrt{p}$. By transitivity this implies $$d>p-2\sqrt{p}.$$

We now have $d<p-2\sqrt{p}$ and $d>p-2\sqrt{p}$. This is a clear contradiction, which proves the lemma.

Because $p \equiv 1 \pmod 4$, there exists some $a \in \mathbb{U}_p$ such that $a^2 \equiv -1 \pmod p$. By the lemma there exist $x,y \in \{1,2,\dots,n\}$ such that $ax \equiv \pm y \pmod p$. Squaring this we get $-x^2 \equiv y^2 \pmod p$ so $p \mid (x^2 + y^2)$. Since $0<x,y<\sqrt{p}$ then this implies that $p = x^2 + y^2$. $\Box$