[proofplan] The forward direction is immediate from [Legendre Symbol of $-1$](/theorems/1717): if $p = x^2 + y^2$ with $p$ odd, then $-1$ is a quadratic residue modulo $p$, forcing $p \equiv 1 \pmod 4$. The converse uses Thue's lemma (a pigeonhole argument in the box $[0, \lfloor\sqrt p\rfloor]^2$) to produce integers $a, b$, not both zero, with $|a|, |b| < \sqrt p$ and $a \equiv s b \pmod p$, where $s$ is a square root of $-1$ modulo $p$ provided by the hypothesis $p \equiv 1 \pmod 4$. Then $a^2 + b^2$ is a positive multiple of $p$ strictly less than $2p$, hence equals $p$. [/proofplan] [step:Establish the forward direction via quadratic reciprocity of $-1$] Suppose $p = x^2 + y^2$ for some $x, y \in \mathbb{Z}$. Since $p$ is an odd prime, $p$ does not divide both $x$ and $y$: if $p \mid x$ and $p \mid y$, then $p^2 \mid x^2 + y^2 = p$, contradicting $p \ge 3$. Without loss of generality $p \nmid y$, so $y$ is a unit modulo $p$; let $z \in \mathbb{Z}$ satisfy $yz \equiv 1 \pmod p$. From $x^2 + y^2 \equiv 0 \pmod p$ we obtain $(xz)^2 \equiv -(yz)^2 \equiv -1 \pmod p$. Hence $-1$ is a quadratic residue modulo $p$, i.e. $\left(\frac{-1}{p}\right) = 1$. By [Legendre Symbol of $-1$](/theorems/1717), this happens exactly when $p \equiv 1 \pmod 4$. [/step] [step:Produce a square root of $-1$ modulo $p$ from $p \equiv 1 \pmod 4$] Conversely, suppose $p \equiv 1 \pmod 4$. By [Legendre Symbol of $-1$](/theorems/1717), $\left(\frac{-1}{p}\right) = +1$, so there exists $s \in \mathbb{Z}$ with \begin{align*} s^2 \equiv -1 \pmod{p}. \end{align*} We will use $s$ to extract a representation $p = a^2 + b^2$. [/step] [step:Apply a pigeonhole argument to find a small non-zero pair $(a, b)$ with $a \equiv s b \pmod p$] Let $m = \lfloor \sqrt{p} \rfloor$, so $m \ge 1$ and $m^2 \le p < (m+1)^2$. Consider the map \begin{align*} \Phi : \{0, 1, \dots, m\}^2 &\to \mathbb{Z}/p\mathbb{Z} \\ (u, v) &\mapsto u - s v \pmod p. \end{align*} The domain has $(m + 1)^2$ elements, and $(m + 1)^2 > p = |\mathbb{Z}/p\mathbb{Z}|$. By the pigeonhole principle, there exist distinct pairs $(u_1, v_1) \ne (u_2, v_2)$ in $\{0, \dots, m\}^2$ with $\Phi(u_1, v_1) = \Phi(u_2, v_2)$, i.e. \begin{align*} u_1 - s v_1 \equiv u_2 - s v_2 \pmod p. \end{align*} Set $a = u_1 - u_2$ and $b = v_1 - v_2$. Then $(a, b) \ne (0, 0)$ and \begin{align*} a \equiv s b \pmod{p}, \qquad |a| \le m, \quad |b| \le m. \end{align*} [/step] [step:Show $a^2 + b^2$ is a positive multiple of $p$ strictly less than $2p$] From $a \equiv s b \pmod p$ and $s^2 \equiv -1 \pmod p$, \begin{align*} a^2 + b^2 \equiv s^2 b^2 + b^2 \equiv (-1 + 1) b^2 \equiv 0 \pmod{p}. \end{align*} So $p \mid a^2 + b^2$. We next bound $a^2 + b^2$: \begin{align*} 0 < a^2 + b^2 \le m^2 + m^2 = 2 m^2 \le 2 p, \end{align*} where strict positivity uses $(a, b) \ne (0, 0)$. If equality $a^2 + b^2 = 2 p$ held, then $m^2 = p$, so $p$ would be a perfect square, contradicting primality of $p$. Therefore $0 < a^2 + b^2 < 2 p$. Combined with $p \mid a^2 + b^2$, this forces $a^2 + b^2 = p$. Hence $p = a^2 + b^2$ with $a, b \in \mathbb{Z}$, completing the converse direction. [guided] We have $s \in \mathbb{Z}$ with $s^2 \equiv -1 \pmod p$ and must produce integers $a, b$ with $a^2 + b^2 = p$. The strategy is to find $a, b$ with two properties: (i) $a \equiv s b \pmod p$, which forces $a^2 + b^2 \equiv (s^2 + 1) b^2 \equiv 0 \pmod p$, and (ii) $|a|, |b|$ small enough that $a^2 + b^2 < 2 p$, pinning the value to the unique positive multiple $p$ of $p$ in the interval $(0, 2p)$. Why "small enough" means $|a|, |b| \le \sqrt{p}$: this gives $a^2 + b^2 \le 2 p$, which together with $(a,b) \ne (0,0)$ forces $a^2 + b^2 \in \{p, 2p\}$. The pigeonhole argument produces the pair. Set $m = \lfloor \sqrt p \rfloor$. Consider the map \begin{align*} \Phi : \{0, 1, \dots, m\}^2 &\to \mathbb{Z}/p\mathbb{Z} \\ (u, v) &\mapsto u - s v \pmod p. \end{align*} Why this specific map? Because if $\Phi(u_1, v_1) = \Phi(u_2, v_2)$, the difference $(a, b) := (u_1 - u_2, v_1 - v_2)$ satisfies $a \equiv s b \pmod p$ automatically — exactly condition (i). The domain of $\Phi$ has $(m+1)^2$ elements. We need $(m+1)^2 > p$: since $m = \lfloor \sqrt p \rfloor$, we have $m + 1 > \sqrt p$, hence $(m+1)^2 > p$, strictly. By the pigeonhole principle applied to $\Phi$, there exist distinct pairs $(u_1, v_1) \ne (u_2, v_2)$ in $\{0, \dots, m\}^2$ with the same image. Setting $a = u_1 - u_2$ and $b = v_1 - v_2$ gives $a \equiv s b \pmod p$, $|a| \le m$, $|b| \le m$, and $(a, b) \ne (0, 0)$. Now we verify the two conclusions: **Divisibility:** Since $s^2 \equiv -1 \pmod p$, \begin{align*} a^2 + b^2 \equiv s^2 b^2 + b^2 \equiv (s^2 + 1) b^2 \equiv 0 \pmod{p}. \end{align*} So $p \mid a^2 + b^2$. **Bounds:** $(a, b) \ne (0, 0)$ gives $a^2 + b^2 > 0$. Also $|a|, |b| \le m$, so \begin{align*} a^2 + b^2 \le 2 m^2 \le 2 p. \end{align*} Could $a^2 + b^2 = 2 p$? This would require $a^2 = b^2 = m^2 = p$, making $p$ a perfect square. But $p$ is an odd prime, so $p \ne m^2$. Hence $a^2 + b^2 < 2 p$. **Conclusion:** The positive multiples of $p$ in the open interval $(0, 2 p)$ consist of the single value $p$. Thus $a^2 + b^2 = p$. A final remark: why did we choose $u, v \in \{0, \dots, m\}$ rather than $\{-m, \dots, m\}$? The asymmetric range maximises the density of the domain: $(m + 1)^2$ over $p$, giving an "extra" $(m+1)^2 - p > 0$ collisions. Using a symmetric range would not save anything and would complicate the size bound on the difference. [/guided] [/step]