📂整数論

4で割ったときに余りが1になる素数の必要十分条件

定理

$p \ne 2$ を 素数 だとしよう。

ある $a,b \in \mathbb{Z}$ について $p \equiv 1 \pmod{4}$ $\iff$ $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 )$

パート 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$ と言える。

---

パート 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}$ だからその存在は常に保証されている）。そうすると、パート 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$ の倍数でなければならないが、パート 1 で $M < p$ であることを示しているから、これは不可能であり、$r$ は少なくとも $0$ よりも大きくなければならない。要約すると、$1 \le r < M$ である。

---

パート 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$ の倍数である。また、上記のパート 2 で述べた $( uA + vB ) \equiv AA + BB \equiv 0 \pmod{M}$ なので、$( uA + vB )$ も $M$ の倍数である。

---

パート 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$$ を得る。上記のパート 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$$ を得る。よって、このような $A_{k}, B_{k}, M_{k}$ はパート 1~3 で定義された $A, B, M$ と同じ性質を持つ。

上記のパート 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$

参考

• 素数を 3 で割った余りが 1 になる必要十分条件