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}$につ