[proofplan] The proof is by two directions. For the forward direction, an integer $N = x^2 + y^2$ divisible by a prime $p \equiv 3 \pmod 4$ forces $p$ to divide both $x$ and $y$: otherwise the relation $x^2 \equiv -y^2 \pmod p$ would yield a square root of $-1$ in $\mathbb{F}_p^\times$, which is impossible because $\left(\frac{-1}{p}\right) = -1$ when $p \equiv 3 \pmod 4$. An inductive descent on the $p$-adic valuation then shows $\nu_p(N)$ is even. For the converse direction, a factorisation $N = M^2 N_1$ with $N_1$ squarefree and all prime factors of $N_1$ equal to $2$ or $\equiv 1 \pmod 4$ reduces the problem, via the Brahmagupta–Fibonacci identity $(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2$ and the explicit representation $2 = 1^2 + 1^2$, to the special case of a single prime $p \equiv 1 \pmod 4$. That special case — every prime $p \equiv 1 \pmod 4$ is a sum of two squares — is cited from the classification of reduced positive definite binary quadratic forms of discriminant $-4$. [/proofplan] [step:State the forward direction and set up the descent] Suppose $N \geq 1$ can be written as $N = x^2 + y^2$ with $x, y \in \mathbb{Z}$. Let $p$ be a prime with $p \equiv 3 \pmod 4$ and $p \mid N$. We show $\nu_p(N) \geq 2$, and more generally that $\nu_p(N)$ is even. Since $p \mid N = x^2 + y^2$, \begin{align*} x^2 + y^2 &\equiv 0 \pmod p, \qquad \text{i.e.,} \qquad x^2 \equiv -y^2 \pmod p. \end{align*} [/step] [step:Force $p \mid y$ using the non-residue $-1$ modulo $p$] We claim $p \mid y$. Suppose for contradiction $p \nmid y$. Then the class of $y$ in $\mathbb{F}_p^\times = (\mathbb{Z}/p\mathbb{Z})^\times$ is a unit, so there exists $z \in \mathbb{Z}$ with $yz \equiv 1 \pmod p$ (by [Bezout's Lemma](/theorems/???) applied to $\gcd(y, p) = 1$, or equivalently by the existence of inverses in the field $\mathbb{F}_p$). Multiplying $x^2 \equiv -y^2 \pmod p$ by $z^2$: \begin{align*} (xz)^2 &\equiv -(yz)^2 \equiv -1 \pmod p. \end{align*} Hence $-1$ is a quadratic residue modulo $p$, i.e., $\left(\frac{-1}{p}\right) = +1$. But by the [Legendre symbol at $-1$](/theorems/???) (or equivalently Euler's criterion applied to $-1$), for odd primes $p$, \begin{align*} \left(\frac{-1}{p}\right) &= (-1)^{(p-1)/2}, \end{align*} which equals $-1$ precisely when $p \equiv 3 \pmod 4$. Since $p \equiv 3 \pmod 4$ by hypothesis, $\left(\frac{-1}{p}\right) = -1$, contradicting $\left(\frac{-1}{p}\right) = +1$. Therefore $p \mid y$. [/step] [step:Deduce $p \mid x$ and $p^2 \mid N$] From $p \mid y$ we obtain $p \mid y^2$, so the congruence $x^2 \equiv -y^2 \pmod p$ yields $x^2 \equiv 0 \pmod p$. Since $p$ is prime, $p \mid x$. Write $x = p x'$ and $y = p y'$ with $x', y' \in \mathbb{Z}$. Then \begin{align*} N &= x^2 + y^2 = p^2 (x'^2 + y'^2), \end{align*} so $p^2 \mid N$ and $N / p^2 = x'^2 + y'^2$ is itself a sum of two squares. [guided] We have a self-similar recursion: starting from $N = x^2 + y^2$ with $p \mid N$, we extracted a factor of $p^2$ and obtained a strictly smaller integer $N/p^2 = x'^2 + y'^2$ that is still a sum of two squares. The argument can be repeated on $N/p^2$. Why did we need both $p \mid x$ and $p \mid y$, rather than just $p \mid N$? Because to factor out $p^2$ from the representation $N = x^2 + y^2$, we must write both squares as squares of multiples of $p$. The crucial step was the non-residue property of $-1$ modulo $p \equiv 3 \pmod 4$: if $p \nmid y$, then $-1$ would be a non-zero square in $\mathbb{F}_p$, which is false for $p \equiv 3 \pmod 4$. [/guided] [/step] [step:Complete the forward direction by induction on $\nu_p(N)$] Let $e = \nu_p(N)$. We prove by strong induction on $e$ that $e$ is even. The case $e = 0$: $e$ is even, and there is nothing to prove. The case $e \geq 1$: By Steps 1–3, $p^2 \mid N$, and writing $N' = N/p^2 = x'^2 + y'^2$, $N'$ is a sum of two squares with $\nu_p(N') = e - 2$. By the inductive hypothesis applied to $N'$ (which has smaller $p$-adic valuation), $\nu_p(N') = e - 2$ is even, hence $e = \nu_p(N)$ is even. This completes the forward direction: every prime $p \equiv 3 \pmod 4$ dividing $N$ does so to an even power. [/step] [step:Set up the converse: reduce $N$ to a squarefree core with favourable prime factors] Suppose $N \geq 1$ is a positive integer such that every prime $p \equiv 3 \pmod 4$ with $p \mid N$ satisfies $\nu_p(N)$ even. Write \begin{align*} N &= M^2 N_1, \end{align*} where $M \in \mathbb{Z}_{\geq 1}$ absorbs all squared factors and $N_1 \in \mathbb{Z}_{\geq 1}$ is squarefree. Explicitly, for each prime $p \mid N$ with $\nu_p(N) = 2a + b$ (where $b \in \{0, 1\}$), place $p^{a}$ in $M$ and $p^{b}$ in $N_1$. By the hypothesis, primes $p \equiv 3 \pmod 4$ have $\nu_p(N)$ even, hence $b = 0$, meaning $p \nmid N_1$. Therefore every prime factor of $N_1$ is either $2$ or $\equiv 1 \pmod 4$. If we can write $N_1 = u^2 + v^2$ for some integers $u, v$, then \begin{align*} N &= M^2 N_1 = M^2 (u^2 + v^2) = (Mu)^2 + (Mv)^2, \end{align*} exhibiting $N$ as a sum of two squares. Hence it suffices to prove that every squarefree positive integer $N_1$ whose prime factors are $2$ or $\equiv 1 \pmod 4$ is a sum of two squares. [/step] [step:Record the multiplicative structure (Brahmagupta–Fibonacci identity)] The set $S \subseteq \mathbb{Z}_{\geq 0}$ of integers expressible as a sum of two squares is closed under multiplication, by the [Brahmagupta–Fibonacci Identity](/theorems/???): \begin{align*} (a^2 + b^2)(c^2 + d^2) &= (ac - bd)^2 + (ad + bc)^2. \end{align*} This identity is verified by direct expansion: \begin{align*} (ac - bd)^2 + (ad + bc)^2 &= a^2 c^2 - 2abcd + b^2 d^2 + a^2 d^2 + 2abcd + b^2 c^2 \\ &= a^2(c^2 + d^2) + b^2 (c^2 + d^2) \\ &= (a^2 + b^2)(c^2 + d^2). \end{align*} Consequently, if every prime factor of $N_1$ is a sum of two squares, then $N_1$ itself is a sum of two squares (by induction on the number of prime factors of $N_1$, using the fact that $N_1$ is squarefree so its prime factorisation has no repetition). [guided] The Brahmagupta–Fibonacci identity is the statement that $S$ is a submonoid of $\mathbb{Z}_{\geq 0}$ under multiplication. In Gaussian-integer language, it reflects $|zw|^2 = |z|^2 |w|^2$ for $z = a + bi$ and $w = c + di$: the norm $|z|^2 = a^2 + b^2$ is multiplicative, and $|zw|^2 = |ac - bd + i(ad + bc)|^2$ gives the explicit sum-of-two-squares representation on the right. Why does this suffice? Because $N_1$ factors as a product of primes of "good type" (either $2$ or $\equiv 1 \pmod 4$). If each such prime is a sum of two squares, then by closure under multiplication, so is any product of them. The case of squarefree $N_1$ is what we have reduced to; but in fact the argument shows that any product of good primes (with any multiplicities) is a sum of two squares. [/guided] [/step] [step:Dispatch the prime factor $2$] The identity \begin{align*} 2 &= 1^2 + 1^2 \end{align*} exhibits $2$ as a sum of two squares. [/step] [step:Dispatch primes $p \equiv 1 \pmod 4$ via binary quadratic forms of discriminant $-4$] Let $p$ be a prime with $p \equiv 1 \pmod 4$. We apply the [Classification of Reduced Positive Definite Binary Quadratic Forms of Discriminant $-4$](/theorems/???): the unique reduced positive definite integral binary quadratic form of discriminant $-4$ is \begin{align*} f_0(x, y) &= x^2 + y^2. \end{align*} We must check the hypotheses under which this result yields a representation of $p$. First, $p \equiv 1 \pmod 4$ implies $\left(\frac{-1}{p}\right) = +1$ (by the formula $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$, which equals $+1$ when $p \equiv 1 \pmod 4$). Hence $-1$ is a square modulo $p$, so by the [representability criterion for binary quadratic forms of discriminant $d$](/theorems/???), $p$ is represented by some positive definite form of discriminant $-4$. Since the only reduced such form is $f_0 = x^2 + y^2$ and every form is [equivalent](/theorems/1726) to a reduced form, there exist $x, y \in \mathbb{Z}$ with \begin{align*} p &= x^2 + y^2. \end{align*} [guided] The final ingredient of the proof is the classical fact — due to Fermat in this form — that every prime $p \equiv 1 \pmod 4$ is a sum of two squares. The cleanest proof uses the theory of reduced positive definite binary quadratic forms: - The discriminant $d = -4$ is possible ($d \equiv 0 \pmod 4$). - A positive definite integer form $ax^2 + bxy + cy^2$ of discriminant $-4$ is reduced precisely when $|b| \leq a \leq c$ and either $b = 0$ or $|b| < a$; combined with $b^2 - 4ac = -4$, a finite computation shows the only solution is $(a, b, c) = (1, 0, 1)$, i.e., the form $x^2 + y^2$. - The class number of discriminant $-4$ is therefore $1$: every positive definite form of that discriminant is equivalent to $x^2 + y^2$. - A prime $p$ is represented by some form of discriminant $-4$ if and only if $-4$ is a quadratic residue modulo $4p$, which reduces (for odd $p$) to $-1$ being a quadratic residue modulo $p$, i.e., $p \equiv 1 \pmod 4$. - Combining: primes $p \equiv 1 \pmod 4$ are represented by $x^2 + y^2$, so $p = x^2 + y^2$ for some $x, y \in \mathbb{Z}$. We have pulled each hypothesis into scope: $p \equiv 1 \pmod 4$ implies $\left(\frac{-1}{p}\right) = +1$ by the [Legendre symbol at $-1$](/theorems/???), and class number one for discriminant $-4$ gives the single representative $x^2 + y^2$. The required chain of theorems on binary quadratic forms is treated in the sections of the notes that follow this theorem; we cite it by name here and record that the full hypotheses-verification is carried out in those subsequent proofs. [/guided] [/step] [step:Assemble the converse and conclude] Combining Steps 5, 6, 7, and 8: every prime factor of $N_1$ (namely $2$ or primes $\equiv 1 \pmod 4$) is a sum of two squares; the set of sums of two squares is closed under multiplication by the Brahmagupta–Fibonacci identity; $N_1$, being squarefree with such prime factors, is a product of these primes. Hence $N_1$ is a sum of two squares, and consequently so is $N = M^2 N_1$. Together with the forward direction (Steps 1–4), this establishes: $N$ is a sum of two squares if and only if every prime $p \equiv 3 \pmod 4$ dividing $N$ does so to an even power. [/step]