素数を4で割った余りが1になる必要十分条件
定理
$p \ne 2$を素数としよう。
$p \equiv 1 \pmod{4}$ $\iff$ ある$a,b \in \mathbb{Z}$に対して$p = a^2 + b^2$
説明
$p=2$は除外したが、実は$ 2= 1^2 + 1^2$なので、定理に含まれても大した問題はない。
例えば$13 \equiv 1 \pmod{4}$は $$ 13 = 4 + 9 = 2^2 + 3^2 $$ $37 \equiv 1 \pmod{4}$は $$ 37 = 1 + 36 = 1^2 + 6^2 $$ $61 \equiv 1 \pmod{4}$は $$ 61 = 25 + 36 = 5^2 + 6^2 $$ である。このような事実はそれ自体でも興味深いが、ガウス素数と深い関連があり、数論を一段高い次元へと導く。
証明
$( \implies )$
Part 1.
$p \equiv 1 \pmod{4}$なので、ある$k \in \mathbb{N}$に対して$p = 4k +1$と表すことができる。
オイラーの判定法: $\displaystyle a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}$
オイラーの判定法により $$ \left( {{-1} \over {p}} \right) \equiv (-1)^{ {{ (4k + 1 ) - 1 } \over {2}} } \equiv (-1)^{2k} \equiv 1 \pmod{p} $$ したがって$-1$は$p$における平方剰余であり、$c^{2} \equiv -1 \pmod{p}$を満たす$c \in \mathbb{Z}$が存在する。両辺に$B^2$を掛けて移項すると $$ (cB)^2 + B^2 \equiv 0 \pmod{ p } $$ である。$A := (cB)$とおくと、ある$M \in \mathbb{Z}$に対して $$ A^2 + B^2 = Mp $$ であり $$ M = {{ A^2 + B^2 } \over {p}} \le {{ (p-1)^2 + 1^2 } \over {p}} = p - {{ 2p - 2 } \over {p}} < p $$ なので$M < p$である。この$M$を縮小し続けて$M=1$になれば、ある$a,b \in \mathbb{Z}$に対して$p = a^2 + b^2$と言える。
Part 2. $1 \le r < M$
$$ u \equiv A \pmod{M} \\ v \equiv B \pmod{M} \\ - {{M} \over {2}} \le u,v \le {{M} \over {2}} $$ を満たす$u,v \in \mathbb{Z}$を考えてみよう（例えば$M=13$で$A \equiv 10 \pmod{13}$ならば$u \equiv -3 \pmod{13}$なので、その存在性は常に保証されている）。すると、Part 1で$A^2 + B^2 = pM$だったので $$ u^2 + v^2 \equiv A^2 + B^2 \equiv 0 \pmod{M} $$ であり、ある$r \in \mathbb{Z}$に対して$u^2 + v^2 = rM$である。また $$ r = {{ u^2 + v^2 } \over {M}} \le {{ (M/2)^2 + (M/2)^2 } \over { M }} = { { M } \over { 2 } } < M $$ なので$r < M$である。
ここで$r = 0$と仮定すると$\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$なので、$A, B$は$M$の倍数であり、$A^2 + B^2$は$M^2$の倍数でなければならない。つまり$M$が$p$の倍数でなければならないが、Part 1で$M < p$であることを示したのでこれは不可能であり、$r$は少なくとも$0$よりは大きくなければならない。まとめると$1 \le r < M$である。
Part 3.
コーシー・シュワルツの等式により $$ \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*} $$ なので$( uA - vB )$は$M$の倍数である。また、上のPart 2で$( uA + vB ) \equiv AA + BB \equiv 0 \pmod{M}$なので$( uA + vB )$も$M$の倍数である。
Part 4.
$A^2 + B^2 = Mp$であり$u^2 + v^2 = Mr$なので $$ (u^2 + v^2) ( A^2 + B^2 ) = M^2 r p $$ であり、コーシー・シュワルツの等式を用いると $$ ( uA + vB )^2 + ( uA - vB )^2 = M^2 r p $$ を得る。上のPart 3で$( uA + vB )$と$( uA - vB )$は$M$の倍数なので、両辺を$M^2$で割ると $$ \left( {{ uA + vB } \over {M}} \right)^2 + \left( {{ uA - vB } \over {M}} \right)^2 = r p $$ これに対して新しく $$ A_{2} : = \left( {{ uA + vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r $$ を定義すると、再び $$ A_{2}^{2} + B_{2}^{2} = M_{2} p $$ を得る。したがって、$k \in \mathbb{N}$に対してこのような$A_{k}, B_{k}, M_{k}$はPart 1~3で定義した$A, B, M$と同じ性質を持つ。
上のPart 2で$r < M$だったので、$M_{k}$は$k$が増加するたびに小さくなり、$1 \le r$なのでちょうど$M=1$で止まる。
$( \impliedby )$
$p=a^2 + b^2$は奇数なので、$a$と$b$が両方とも偶数、あるいは両方とも奇数であることはありえない。
ある$n , m \in \mathbb{Z}$に対して$a := 2n +1 $、$b = 2m$としよう。すると $$ \begin{align*} p =& a^2 + b^2 \\ =& 4n^2 + 4n + 1 + 4m^2 \\ =& 4 ( n^2 + n + m ) +1 \end{align*} $$ なので、$p \equiv 1 \pmod{4}$である。
■
上のコーシー・シュワルツの等式を応用し、いくつかの条件をさらに加えれば、自然数に対しても同様の系を得ることができる。
系
奇数$m$のすべての素因数を$4$で割った余りが$1$であるか、あるいは偶数$m$に対して$\displaystyle {{m} \over {2}}$が奇数であり$\displaystyle {{m} \over {2}}$のすべての素因数を$4$で割った余りが$1$ $\iff$ $\gcd ( a,b) =1$を満たす$a,b \in \mathbb{Z}$に対して$m = a^2 + b^2$