素数を3で割った余りが1になる必要十分条件
定理
$p \ne 3$が素数だとしよう。 $p \equiv 1 \pmod{3}$ $\iff$ ある$a,b \in \mathbb{Z}$に対して$p = a^2 - ab + b^2$
説明
$p=3$は除外したが、実際には$ 3= 2^2 - 2 \cdot 1 + 1^2$なので、定理に含まれていても大した問題はない。
例えば$13 \equiv 1 \pmod{4}$は $$ 13 = 1 - 4 + 16 = 1^2 - 1 \cdot 4 + 4^2 $$ $37 \equiv 1 \pmod{4}$は $$ 37 = 9 -21 + 49 = 3^2 - 3 \cdot 7+ 7^2 $$ $61 \equiv 1 \pmod{4}$は $$ 61 = 16 - 36 + 81 = 4^2 - 4 \cdot 9 + 9^2 $$
このようなファクトはそれ自体でも興味深いが、アイゼンシュタイン整数と深い関わりがあり、数論を一段高い次元へと導く。
証明
$( \implies )$
$$ a^2 + 3 b^2 = ( a + b )^2 - ( a+ b) ( a - b) + (a - b) ^2 $$ なので、$p = a^2 + 3b^2$を満たす$a,b \in \mathbb{Z}$が存在することを示せばよい。
パート1.
$p \equiv 1 \pmod{3}$かつ奇数なので、ある$k \in \mathbb{N}$に対して$p = 6k +1$と表せる。
パート1-1. ガウスの二次互反律
ガウスの二次互反律：相異なる二つの奇数$p , q$に対して
- [2]: $$\left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$
ガウスの二次互反律により $$ \begin{align*} \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) =& (-1)^{ { {p-1} \over {2} }{ {3-1} \over {2} } } \\ =& (-1)^{ {{ (6k + 1) - 1 } \over {2}} } \\ =& (-1)^{3k} \\ =& (-1)^{k} \end{align*} $$
パート1-2. オイラーの判定法
オイラーの判定法：$$a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p}$$
オイラーの判定法により $$ \left( {{-1} \over {p}} \right) \equiv (-1)^{ {{ p - 1 } \over {2}} } \equiv (-1)^{k} \pmod{p} $$
パート1-3. ルジャンドル記号の乗法的性質
ルジャンドル記号の乗法的性質：$2$より大きい素数$p$に対して、$$\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)$$
ルジャンドル記号の乗法的性質により $$ \left( { { 3 } \over { p } } \right) = \left( { { -1 } \over { p } } \right) \left( { { -3 } \over { p } } \right) $$ $p \equiv 1 \pmod{3}$なので、$x^2 \equiv p \pmod{3 }$を満たす$x=1$が存在して $$ \left( { { p } \over { 3 } } \right) = 1 $$ でなければならない。したがって次を得る。 $$ \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = \left( { { -1 } \over { p } } \right) \left( { { -3 } \over { p } } \right) $$
パート1-4.
- ケース1. $k$が偶数
- パート1-1により$\displaystyle \left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = 1$
- パート1-2により$\displaystyle \left( { { -1 } \over { p } } \right) = 1$
- パート1-3により$\displaystyle 1 = 1 \cdot \left( { { -3 } \over { p } } \right)$
- ケース2. $k$が奇数
- パート1-1により$\left( { { p } \over { 3 } } \right) \left( { { 3 } \over { p } } \right) = -1$なので$\displaystyle \left( { { p } \over { 3 } } \right) = - \left( { { 3 } \over { p } } \right)$
- パート1-2により$\left( { { -1 } \over { p } } \right) = -1$なので$\displaystyle \left( { { p } \over { 3 } } \right) = \left( { { -1 } \over { p } } \right) \left( { { 3 } \over { p } } \right) = \left( { { -3 } \over { p } } \right)$
- パート1-3により$\displaystyle 1 = \left( { { -3 } \over { p } } \right)$
どちらの場合でも$-3$は$p$における二次剰余であり、$c^{2} \equiv -3 \pmod{p}$を満たす$c \in \mathbb{Z}$が存在する。両辺に$B^2$を掛けて移項すると $$ (cB)^2 + 3 B^2 \equiv 0 \pmod{ p } $$ となり、$A := (cB)$と置けば、ある$M \in \mathbb{Z}$に対して $$ A^2 + 3 B^2 = Mp $$ である。また $$ M = {{ A^2 + 3 B^2 } \over {p}} \le {{ (p-1)^2 - 3 \cdot 1^2 } \over {p}} = p - {{ 2p - 4 } \over {p}} < p $$ なので$M < p$である。この$M$を減らし続けて$M=1$になれば、ある$a,b \in \mathbb{Z}$に対して$p = a^2 + 3 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 + 3B^2 = pM$だったので $$ u^2 + 3 v^2 \equiv A^2 + 3 B^2 \equiv 0 \pmod{M} $$ であり、ある$r \in \mathbb{Z}$に対して$u^2 + 3 v^2 = rM$である。
パート2-1. $r < M$
$$ r = {{ u^2 + 3 v^2 } \over {M}} \le {{ (M/2)^2 + 3 (M/2)^2 } \over { M }} \le M $$ なので$r \le M$である。
$M = r$となるのは$\displaystyle {{M} \over {2}} = \left| u \right| = \left| v \right| $の場合だけなので $$ u^2 + 3 v^2 = 4u^2 = 4 v^2 = M^2 $$ である。
- ここで$M = | 2u |$は偶数だが、ある$\alpha \in \mathbb{Z}$に対して$u = M \alpha + A = 2 |u| \alpha +A$なので$u \equiv A \pmod{ 2 } $である。
- 同様に$M = | 2v |$であり、ある$ \beta \in \mathbb{Z}$に対して$v = M \beta + B = 2 |v| \beta +B$なので$v \equiv B \pmod{ 2 } $である。
まとめると、$u$と$A$は同時に奇数か偶数でなければならず、$v$と$B$も同時に奇数か偶数でなければならない。これについて $$ A^2 + 3 B^2 = Mp = 2 |u| p $$ という式が成り立ち得るか確認してみよう。
- ケース1. $A$と$B$がともに偶数
$A$が偶数なので、$|u|$も偶数となって$2$で割れる。$A^2 + 3 B^2 = 2 |u| p$の両辺を$4$で割ると $$ \left( {{A} \over {2}} \right) ^2 + 3 \left( {{B} \over {2}} \right) ^2 = \left( {{ | u | } \over {2}} \right) p $$ これはパート1で$A,B,M$を過度に大きく取ったということだ。新しい $$ A ' := \left( {{A} \over {2}} \right) \\ B ' := \left( {{B} \over {2}} \right) \\ M’ := \left( {{ |u| } \over {2}} \right) $$ を取ってパート2をやり直せばよい。 - ケース2. $A$は偶数、$B$は奇数
$A^2 + 3 B^2 = 2 |u| p$の左辺は奇数なのに右辺は偶数なので、式$A^2 + 3 B^2 = Mp$は成り立たない。 - ケース3. $A$は奇数、$B$は偶数
$A^2 + 3 B^2 = 2 |u| p$の左辺は奇数なのに右辺は偶数なので、式$A^2 + 3 B^2 = Mp$は成り立たない。 - ケース4. $A$と$B$がともに奇数 ある$n,m \in \mathbb{Z}$に対して$A := 2n + 1$、$B := 2m +1$と置こう。 $$ A^2 + 3 B^3 = 4n^2 + 4n + 1 + 3( 4 m^2 + 4m + 1 ) = 4( n^2 + n + 3 m^2 + 3m + 1) $$ は$4$の倍数である。しかし$| u |$と$p$は奇数なので、$Mp = 2 | u | p$は$4$の倍数になり得ず、式$A^2 + 3 B^2 = Mp$は成り立たない。
可能なすべての場合を検討すると、ケース2〜4により$r < M$であることがわかる。
パート2-2. $1 \le r$
$r = 0$と仮定すると$\begin{cases} 0 = u \equiv A \pmod{M} \\ 0 = v \equiv B \pmod{M} \end{cases}$なので、$A, B$は$M$の倍数であり、$A^2 + 3 B^2$は$M^2$の倍数でなければならない。すなわち$M$が$p$の倍数でなければならないが、パート1で$M < p$を示したのでこれは不可能である。したがって$r$は$0$より大きくなければならない。
パート2-1とパート2-2を合わせると$1 \le r < M$を得る。
パート3. 変形されたコーシー・シュワルツ等式
$$ \begin{align*} & (u^2 + 3 v^2) ( A^2 + 3 B^2 ) \\ = & u^2 A^2 + 3 v^2 A^2 + 3 u^2 B^2 + 9 v^2 B^2 \\ = & ( u^2 A^2 + 6uAvB + 3v^2 B^2 ) + ( 3 v^2 A^2 - 6uAvB + 3 u^2 B^2 ) \\ = & ( uA + 3 vB )^2 + 3 ( uA - vB )^2 \end{align*} $$ 一方 $$ 3 ( uA - vB ) \equiv 3 ( BA - AB ) \equiv 0 \pmod{M} $$ なので$3 ( uA - vB )$は$M$の倍数である。パート2で $$ ( uA + 3 vB ) \equiv AA + 3 BB \equiv 0 \pmod{M} $$ なので$( uA + 3 vB )$は$M$の倍数である。
パート4.
$A^2 + 3 B^2 = Mp$かつ$u^2 + 3 v^2 = Mr$なので $$ (u^2 + 3 v^2) ( A^2 + 3 B^2 ) = M^2 r p $$ 変形されたコーシー・シュワルツ等式を用いると $$ ( uA + 3 vB )^2 + 3 ( uA - vB )^2 = M^2 r p $$ 上のパート3で$( uA + 3 vB )$と$3 ( uA - vB )$は$M$の倍数なので、両辺を$M^2$で割ると $$ \left( {{ uA + 3 vB } \over {M}} \right)^2 + 3 \left( {{ uA - vB } \over {M}} \right)^2 = r p $$
これに対して新しい $$ A_{2} : = \left( {{ uA + 3 vB } \over {M}} \right) \\ B_{2} := \left( {{ uA - vB } \over {M}} \right) \\ M_{2} := r $$ を定義すれば、再び$A_{2}^{2} + 3 B_{2}^{2} = M_{2} p$を得る。したがって$k \in \mathbb{N}$に対して、このような$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 - ab + b^2$を満たす$a,b$を$3$で割った商が$n,m$だとしよう。
- $N_{0} = 3k + 0$なら $$ N_{0}^{2} \equiv 9k^2 \equiv 0 \pmod{ 3 } $$
- $N_{1} = 3k + 1$なら $$ N_{1}^{2} \equiv \left( 9k^2 + 6k \right) + 1 \equiv 1 \pmod{ 3 } $$
- $N_{2} = 3k + 2$なら $$ N_{0}^{2} \equiv \left( 9k^2 + 12k + 3 \right) + 1 \equiv 1 \pmod{ 3 } $$
したがって$\pmod{3}$において、$3$の倍数でない自然数$N$に対してはいずれにせよ$N^2 \equiv 1 \pmod{ 3 }$である。
これから$a$、$b$が取り得るすべての組み合わせを考えてみよう。
- ケース00. $a= 3n$、$b = 3m$ $$ p = 9 n^2 - 9 nm + 9 m^2 = 3 ( 3 n^2 - 3 nm + 3 m^2) $$ 素数$p$が$3$の倍数になるので、このような組み合わせは不可能である。
- ケース01. $a= 3n$、$b = 3m + 1$ $$p \equiv 9 n^2 - 3n b + b^2 \equiv 1 \pmod{ 3 }$$
- ケース02. $a= 3n$、$b = 3m + 2$ $$p \equiv 9 n^2 - 3n b + b^2 \equiv 1 \pmod{ 3 }$$
- ケース11. $a= 3n + 1$、$b = 3m + 1$ $$p \equiv a^2 - ( 3n + 1 ) ( 3m + 1) + b^2 \equiv 1 - 9nm - 3n - 3m - 1 + 1 \equiv 1 \pmod{3}$$
- ケース12. $a= 3n + 1$、$b = 3m + 2$ $$ \begin{align*} p =& (3n+1)^2 - ( 3n + 1 ) ( 3m + 2 ) + (3m+2)^2 \\ =& 9n^2 + 6n + 1 - 9nm - 6n - 3m - 2 + 9m^2 + 12m + 4 \\ =& 3 ( 3n^2 + 3m^2 - 3nm + 2n + 4m + 1 ) \end{align*} $$ 素数$p$が$3$の倍数になるので、このような組み合わせは不可能である。
- ケース22. $a= 3n + 2$、$b = 3m + 2$ $$ \begin{align*} p \equiv& a^2 - ( 3n + 2 ) ( 3m + 2 ) + n^2 \\ \equiv& 1 - 9nm - 6n - 6m - 4 + 1 \\ \equiv& -2 \\ \equiv& 1 \pmod{3} \end{align*} $$ すべての場合を調べると、ケース01、ケース02、ケース11、ケース22のような場合には$p \equiv 1 \pmod{3}$であり、ケース00、ケース12のような場合は起こらない。
■