Primes That Leave a Remainder of 1 When Divided by 4
Theorem
Let $p \ne 2$ be a prime number.
For some $a,b \in \mathbb{Z}$, $p \equiv 1 \pmod{4}$ $\iff$ $p = a^2 + b^2$
Explanation
While excluding $p=2$, in fact, since it is $ 2= 1^2 + 1^2$, it’s not a big deal to include it in the theorem.
For example, $13 \equiv 1 \pmod{4}$ is $$ 13 = 4 + 9 = 2^2 + 3^2 $$ $37 \equiv 1 \pmod{4}$ is $$ 37 = 1 + 36 = 1^2 + 6^2 $$ $61 \equiv 1 \pmod{4}$ is $$ 61 = 25 + 36 = 5^2 + 6^2 $$ These facts are interesting on their own but also have a deep connection with Gaussian primes, elevating number theory to a higher level.
Proof
$( \implies )$
Part 1.
Since $p \equiv 1 \pmod{4}$, for some $k \in \mathbb{N}$, it can be represented as $p = 4k +1$.
Euler’s Criterion: $\displaystyle a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}$
By Euler’s criterion, $$ \left( {{-1} \over {p}} \right) \equiv (-1)^{ {{ (4k + 1 ) - 1 } \over {2}} } \equiv (-1)^{2k} \equiv 1 \pmod{p} $$ therefore, $-1$ is a quadratic residue in $p$, and there exists $c \in \mathbb{Z}$ satisfying $c^{2} \equiv -1 \pmod{p}$. Multiplying both sides by $B^2$ and rearranging gives $$ (cB)^2 + B^2 \equiv 0 \pmod{ p } $$ Letting $A := (cB)$, for some $M \in \mathbb{Z}$ $$ A^2 + B^2 = Mp $$ and $$ M = {{ A^2 + B^2 } \over {p}} \le {{ (p-1)^2 + 1^2 } \over {p}} = p - {{ 2p - 2 } \over {p}} < p $$ thus $M < p$. Continuously reducing this $M$ to $M=1$ means for some $a,b \in \mathbb{Z}$, $p = a^2 + b^2$ can be said.
Part 2. $1 \le r < M$
Consider $u,v \in \mathbb{Z}$ satisfying $$ u \equiv A \pmod{M} \\ v \equiv B \pmod{M} \\ - {{M} \over {2}} \le u,v \le {{M} \over {2}} $$ (for example, if $M=13$ and $A \equiv 10 \pmod{13}$, then $u \equiv -3 \pmod{13}$, so their existence is always assured). Then, since $A^2 + B^2 = pM$ in Part 1, $$ u^2 + v^2 \equiv A^2 + B^2 \equiv 0 \pmod{M} $$ and for some $r \in \mathbb{Z}$, $u^2 + v^2 = rM$. Also, $$ r = {{ u^2 + v^2 } \over {M}} \le {{ (M/2)^2 + (M/2)^2 } \over { M }} = { { M } \over { 2 } } < M $$ thus $r < M$.
Assuming $r = 0$, since $\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$, $A, B$ must be a multiple of $M$, and $A^2 + B^2$ must be a multiple of $M^2$. That is, $M$ must be a multiple of $p$, but since $M < p$ is shown in Part 1, this is impossible, and $r$ must be at least greater than $0$. Summarizing, $1 \le r < M$.
Part 3.
According to the Cauchy-Schwarz inequality, $$ \begin{align*} & (u^2 + v^2) ( A^2 + B^2 ) \\ =& u^2 A^2 + v^2 A^2 + u^2 B^2 + v^2 B^2 \\ =& ( u^2 A^2 + 2uAvB + v^2 B^2 ) + ( v^2 A^2 - 2uAvB + u^2 B^2 ) \\ =& ( uA + vB )^2 + ( uA - vB )^2 \\ =& ( uA - vB ) \\ \equiv& BA - AB \pmod{M} \\ \equiv& 0 \pmod{M} \end{align*} $$ thus $( uA - vB )$ is a multiple of $M$. Also, since $( uA + vB ) \equiv AA + BB \equiv 0 \pmod{M}$ in the above Part 2, $( uA + vB )$ is also a multiple of $M$.
Part 4.
Since $A^2 + B^2 = Mp$ and $u^2 + v^2 = Mr$, $$ (u^2 + v^2) ( A^2 + B^2 ) = M^2 r p $$ and using the Cauchy-Schwarz inequality, $$ ( uA + vB )^2 + ( uA - vB )^2 = M^2 r p $$ is obtained. Since $( uA + vB )$ and $( uA - vB )$ are multiples of $M$ in the above Part 3, dividing both sides by $M^2$ gives $$ \left( {{ uA + vB } \over {M}} \right)^2 + \left( {{ uA - vB } \over {M}} \right)^2 = r p $$ Defining a new $$ A_{2} : = \left( {{ uA + vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r $$ for this gets us back to $$ A_{2}^{2} + B_{2}^{2} = M_{2} p $$ Therefore, this $A_{k}, B_{k}, M_{k}$ for $k \in \mathbb{N}$ has the same properties defined in Parts 1~3.
Since $r < M$ in the above Part 2, $M_{k}$ decreases as $k$ increases, stopping exactly at $M=1$.
$( \impliedby )$
Since $p=a^2 + b^2$ is odd, $a$ and $b$ cannot both be even or odd.
Let’s say for some $n , m \in \mathbb{Z}$, $a := 2n +1 $, $b = 2m$. Then, $$ \begin{align*} p =& a^2 + b^2 \\ =& 4n^2 + 4n + 1 + 4m^2 \\ =& 4 ( n^2 + n + m ) +1 \end{align*} $$ thus, $p \equiv 1 \pmod{4}$.
■
By applying the Cauchy-Schwarz inequality and adding a few more conditions, a similar corollary can also be obtained for natural numbers.
Corollary
For odd $m$, the remainder when dividing all prime factors by $4$ is $1$, or for even $m$, if $\displaystyle {{m} \over {2}}$ is odd and the remainder when dividing all prime factors of $\displaystyle {{m} \over {2}}$ by $4$ is $1$ $\iff$ $\gcd ( a,b) =1$ for some $a,b \in \mathbb{Z}$, then $m = a^2 + b^2$