📂整数論

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