katsuのブログ

TwitterID:@ikahakatsu

魔法のような素数判定法！！

この記事は日曜数学 Advent Calender 2024 12日目の参加記事です。

 

HNP!! (Hello New Prime!!)

2024年の個人的な一大ニュースの一つは、素数と判定された最大の数が更新されたことでしょうか。なんとその数は

2^{136279841} - 1

と4000万桁ほどもあるとんでもなく大きい数だそうです。ここで、今まではどんな数が最大の素数と知られている数であったかというと、なんと実は30年もこの 2^p - 1 という形をしたMersenne数という数がトップに居続けているのです（3年間ほど他の素数に抜かされた時期はあれど、それを抜けばなんと70年以上もMersenne素数がトップを維持し続けています！！）。

では一体なぜMersenne素数が素数判定にこれほどまで強いのでしょうか？その大きな理由の一つは次の素数判定法にあります。

 

数列 S_n を

S_1=4, S_{i+1} = S_i^2 -2

により定める。このとき次が成り立つ。

Lucas-Lehmer テスト
 奇素数 p に対して

2^p-1 | S_{p-1} \Longrightarrow 2^p-1 が素数

 

なんだって！！！？？？？

この驚きの判定法によってMersenne数の2の肩に乗ってる数だけ漸化式を計算することで素数判定ができてしまうのです！！

この定理だけでも驚きですが、実はこの定理はPell方程式の解の加法定理に注目することによって、魔法のように一瞬で示せてしまうのです。

今回はそんなクリスマスにお似合いな魔法のような証明を紹介します！！

 

 

Pell方程式による橋渡し

Pell方程式

x^2 -3y^2 = 1

という方程式の n 番目の自然数解をx_n, y_nとすると

(2+\sqrt{3})^n = x_n + \sqrt{3}y_n

と書けることが知られている。

(2+\sqrt{3})^{-1} = 2-\sqrt{3}

に気を付けると、整数 n, m \gt 0 に対し

(2+\sqrt{3})^{n \pm m} = (x_n + \sqrt{3}y_n)(x_m \pm \sqrt{3}y_m)

= (x_nx_m \pm 3y_ny_m)+\sqrt{3}(\pm x_ny_m+x_my_n)

であるので、減法公式の時は n-m \gt 0 となるようにすれば

x_{n\pm m}=x_nx_m \pm 3y_ny_m

y_{n\pm m}=\pm x_ny_m + x_my_n

なる加法公式が成り立つことが分かる。特に n=m なら 2倍公式

x_{2n} = x_n^2 + 3y_n^2 = x_n^2 + (x_n^2 - 1) = 2x_n^2 -1

y_{2n} = 2x_ny_n

を得る。すると、 x_n に関する 2倍公式の両辺を 2 倍することで 2x_{2^n} が S_n と同じ漸化式を持つことがわかる。さらに、 2x_{2^0}=S_1 なので 2x_{2^{n-1}} = S_n となり、2^p - 1 は奇数なので、Lucas-Lehmer テストは

2^p-1 | x_{2^{p-2}} \Longrightarrow 2^p - 1 は素数

とPell方程式の自然数解の言葉で書き直すことができるのである！

 

Lucas-Lehmer テスト

Lucas-Lehmer テストの証明のために以下の二つの補題を紹介する。補題1の証明は計算が重いので、大変であれば一度主張を認め飛ばしてもよい。

 

q を奇素数とする。

y_{\frac{q+1}{2}}y_{\frac{q-1}{2}} \equiv 0 \mod q

証明:

x_n - \sqrt{3}y_n = (x_n + \sqrt{3}y_n)^{-1}

= (2+\sqrt{3})^{-n} = (2-\sqrt{3})^n

であり、

2+\sqrt{3} = \frac{(1+\sqrt{3})^2}{2}, 2-\sqrt{3} = \frac{(1-\sqrt{3})^2}{2}

なので、t = (q+1)/2とすると

x_t = \frac{1}{2}\left( \frac{1}{2^t}(1+\sqrt{3})^{q+1} + \frac{1}{2^t}(1-\sqrt{3})^{q+1} \right)

=\frac{1}{2^t}\sum\limits_{k=0}^{t} \dbinom{q+1}{2k}3^k

y_t = \frac{1}{2\sqrt{3}}\left( \frac{1}{2^t}(1+\sqrt{3})^{q+1} - \frac{1}{2^t}(1-\sqrt{3})^{q+1} \right)

=\frac{1}{2^t}\sum\limits_{k=0}^{t-1} \dbinom{q+1}{2k+1}3^k

となる。ここで、

\dbinom{q+1}{m} = \dbinom{q}{m} + \dbinom{q}{m-1}

なので、

x_t \equiv 1 + 3^t \mod q

y_t \equiv (q+1) + (q+1)3^{t-1} \equiv 1 + 3^{t-1} \mod q

と分かる。よって、加法公式

y_{n-1} = -x_n+2y_n

を利用すると

2^ty_t2^ty_{t-1} = 2^ty^t2^t(-x_t+2y_t)

\equiv (1+3^{t-1})(-1-3^t+2+2\cdot3^{t-1}) \mod q

=(1+3^{t-1})(1-3^{t-1})

= 1 - 3^{2t-2} = 1 - 3^{q-1}

\equiv 0 \mod q

となる。よって、q は奇素数であることから、

y_{t}y_{t-1} = y_{\frac{q+1}{2}}y_{\frac{q-1}{2}} \equiv 0 \mod q

が分かる。

□

 

w を y_{w} \equiv 0 \mod q となる最小の正の整数とする。

なら、補題1は y_{\frac{q+1}{2}} か y_{\frac{q-1}{2}} のどちらかが q で割り切れるということを主張しているので、 w の最小性から 2w \leq q+1 が分かる。

 

y_n \equiv 0 \mod q \iff w|n

証明:

x_0 = 1, y_0 = 0 としても加法公式が成り立つことに注意する。

\Leftarrow について: 整数 k により n = kw とすれば加法公式より

y_{n} = y_{(k-1)w + w} = x_{(k-1)w}y_w + x_wy_{(k-1)w}

なので帰納法より分かる。

\Rightarrow について: 整数 k と 整数 0 \leq r \lt w により n = kw + r とすれば加法公式より

y_{n} = x_{kw}y_r + x_ry_{kw}

であり、上の議論より y_{kw} \equiv 0 なので仮定と合わせると

0 \equiv y_{n} \equiv x_{kw}y_r \mod q

となる。 さらに、 x_{kw}^2 + 3y_{kw}^2 = 1 より x_{kw} と y_{kw} は互いに素なので x_{kw} \not\equiv 0 \mod q であることから、

y_r \equiv 0 \mod q

となり、 r\neq 0 なら w の最小性に矛盾する。よって r=0 なので w|n となる。

□

 

これらを用いてLucas-Lehmer テストを証明する。

Lucas-Lehmer テストの証明:

q を 2^p-1 の素因数とする。なら仮定より q|x_{2^{p-2}} であるので、2倍公式より

y_{2^{p-1}} = 2x_{2^{p-2}}y_{2^{p-2}} \equiv 0 \mod q

となる。w を y_{w} \equiv 0 \mod q となる最小の正の整数とすると x_{2^{p-2}} と y_{2^{p-2}} は互いに素なので q \not| y_{2^{p-2}} より、補題2から w = 2^{p-1} と分かる。よって q の定義から q \leq 2^p -1 であることと、補題1より

q+1 \geq 2w = 2^{p} \geq q +1

つまり、

q = 2^p - 1

であることが分かるので、2^p -1 が素数であることが分かる。

□

 

さいごに

Pell方程式の解における加法公式という驚きのテクニックによって、信じられない定理が一瞬に示されてしまう様子はいかがだったでしょうか？

実は今回紹介したLucas-Lehmer テストは逆も成り立つことが知られています！！（証明が気になる方は参考文献の本やWikipediaなどを参照してみてください。）

この記事によりMersenne素数が神秘的で奥深い世界の入り口になっていることが伝われば幸いです。

 

参考文献

和田 秀男 著, 数の世界 整数論への道

www.iwanami.co.jp

 

t5k.org

 

691の大冒険

概要

 

今回の目的は非正則素数とBernoulli数の関係についての定理, Herbrand-Ribetの定理を691という素数に限ってMazurの視点とともに証明し, そこで出てくる様々な数論の概念や現象について観察することである. 群論や環論, (有限次)Galois理論などの代数学や線形代数, 位相空間論, 初等的な解析学は前提知識としているが, その他必要な知識は付録Aにつけた. さらに各節を読むときに必要な付録Aの番号をその節の最初に書いているので, もし知らない知識であれば適宜参照して欲しい.

 

こちらは都内数学科学生集合(@tosuu_set)で発表したときの発表資料です。

発表を聞いてくださった方々や誤植訂正を手伝ってくださった方々に感謝申し上げます。

 

drive.google.com

局所類体論使い方講座 存在定理編

 

今回は局所類体論の存在定理と呼ばれる局所体上のAbel拡大の分類定理の使い方と、その強さを p-進数版のKronecker-Weberの定理

p-進数版のKronecker-Weberの定理
p を素数とする。任意の \mathbb{Q}_p 上有限次Abel拡大は、ある自然数 n が存在して \mathbb{Q}_p(\zeta_n) に含まれる。ここで \zeta_n とは 1 の原始 n 乗根である。

を証明することで見ていく。

 

目次:

 

 

局所体の定義と性質

この節では以下の内容について話す。

  • 局所体の定義。
  • 局所体 K は その整数環の素元 \pi_K と単数群 U_K により K^* = \langle \pi_K \rangle \times U_K という構造をしている。

局所類体論の存在定理は K^* の指数有限開部分群と K 上のAbel拡大が対応するのでここでは K^* の代数構造と位相的な情報が重要になるのである。

上で書いた内容を知っていれば、あるいは認めれば局所類体論の存在定理とKronecker-Weberの定理の証明の流れは追えるはずである。よってもし以下の議論が難しいと感じたり、長い文を読むのが面倒な人は局所類体論の存在定理へと飛んでも大丈夫である。

 

K を代数体、つまり有理数体 \mathbb{Q} 上の有限次拡大体とする。ならその代数体の整数環 \mathcal{O}_K と呼ばれる K の部分環は「任意のイデアルが有限個の素イデアルの積により一意的に表すことができる。」という特徴を持つ。このような環をDedekind環という。これは素因数分解のようなものをイデアルに対して行っていると見れる。よって \mathcal{O}_K の0でないイデアル全体はイデアルの積により半群となる。ここで"0でないイデアル"を "0でない K の有限生成 \mathcal{O}_K-加群" と定義を広げることでイデアルの逆元までを定義に含めることができる。よってこれは群になり、それを J_K と書き分数イデアル群という。

 

整数の世界ではいろんな整数の素因数分解を考えるように、代数体の世界では整数環のイデアルの素イデアル分解を考える。その為に付値と呼ばれる関数を導入する。

 

a\in K^* に対し (a) を a で生成される \mathcal{O}_K-加群つまり分数イデアルとする。この時 (a) の素イデアル分解を

(a)=\prod\limits_{\mathfrak{p}} \mathfrak{p}^{e_{\mathfrak{p}}} 

とする（ここで \mathfrak{p} は全ての素イデアルを走るとして、ほとんど全ての、つまり有限個の例外を除いて、 e_{\mathfrak{p}}=0 である）。この時 \mathfrak{p} 進付値 v_{\mathfrak{p}}: K^* \rightarrow \mathbb{Z} を

v_{\mathfrak{p}}(a) = e_{\mathfrak{p}}

により定める。これは群準同型である。ここで形式的に v_{\mathfrak{p}}(0) = \infty と置くことで v_{\mathfrak{p}} : K \rightarrow \mathbb{Z} \cup \{\infty\} と関数を拡張する。

 

定理（非Archimedes付値）
v_{\mathfrak{p}}: K \rightarrow \mathbb{Z} \cup \{\infty\} は次を満たす。
  1. v_\mathfrak{p}(a) = \infty \iff a =0
  2. v_{\mathfrak{p}}(ab) = v_{\mathfrak{p}}(a) + v_{\mathfrak{p}}(b)
  3. v_{\mathfrak{p}}(a + b) \leq \mathrm{min} \{ v_{\mathfrak{p}}(a), v_{\mathfrak{p}}(b) \}
また、これらの条件を満たす関数を非Archimedes付値という。

 

ここで K 上の \mathfrak{p}-進絶対値を

|a|_\mathfrak{p} = q^{-v_{\mathfrak{p}}(a)}

ここで q=(\mathcal{O}_K:\mathfrak{p}) であり q^{-\infty} = 0 と定める。

なら (,)_{\mathfrak{p}}:K^* \times K^* \rightarrow \mathbb{R} を

(a,b)_{\mathfrak{p}}=|a-b|_{\mathfrak{p}}

で定めればこれは K 上の距離になる。

よってこの距離により K を完備化したものを K_{\mathfrak{p}} とかく。

このように構成される K_{\mathfrak{p}} を（標数0の）局所体という。

特に、 素数 p に対して K = \mathbb{Q}, \mathfrak{p} = (p) の時は K_{\mathfrak{p}} = \mathbb{Q}_p と書き p-進数という。

 

v_{\mathfrak{p}} と (,)_{\mathfrak{p}} は自然に K_{\mathfrak{p}} 上に延長されるのでそれらを再び v_{\mathfrak{p}} と (,)_{\mathfrak{p}} と書くとするとこれらもそれぞれ K_{\mathfrak{p}} 上の非Archimedes付値と距離になる。よって局所体 K_{\mathfrak{p}} をこの距離 (,)_{\mathfrak{p}} による距離空間としても考えることにする。

 

ここで K_{\mathfrak{p}} における整数環のようなものとして

\mathcal{O}_{\mathfrak{p}} = \{ a \in K_{\mathfrak{p}} \mid v_{\mathfrak{p}}(a) \geq 0 \}

を定める。するとこれは局所環（つまり0でない素イデアルを1つしか持たない）で単項イデアル整域、特にDedekind環であることが分かる。ここで \mathcal{O}_{\mathfrak{p}} の0でない素イデアルは

\mathfrak{p}\mathcal{O}_{\mathfrak{p}} = \{ a \in K_{\mathfrak{p}} \mid v_{\mathfrak{p}}(a) \gt 0 \}

という形をしている。

 

ここで局所体が局所体と呼ばれる所以をみてみよう。

分数イデアル I = \prod \mathfrak{p}^{e_{\mathfrak{p}}} の素イデアル分解を考える。

なら

I\mathcal{O}_{\mathfrak{p}} = \mathfrak{p}^{e_{\mathfrak{p}}}\mathcal{O}_{\mathfrak{p}}

が成り立つ。つまり代数体における分数イデアルの \mathfrak{p}-冪という局所的な情報だけ引き出すことができるので局所体と呼ばれる理由もわかるであろう。

 

さて、局所体の性質をもう少し詳しくみる。

 \mathcal{O}_{\mathfrak{p}} は0でない素イデアルを1つしか持たないDedekind環なので任意の分数イデアルは \mathfrak{p}\mathcal{O}_{\mathfrak{p}}-冪で表される。さらに単項イデアル整域なので唯一の0でない素イデアルは素元 \pi_{K_{\mathfrak{p}}} を用いて \mathfrak{p}\mathcal{O}_{\mathfrak{p}} = (\pi_{K_{\mathfrak{p}}}) と書ける。以上のことから任意の a \in K_{\mathfrak{p}}^* に対して n \in \mathbb{Z}_{\geq 0} が存在して

(a) = (\pi_{K_{\mathfrak{p}}}^n)

とできる。よって適当な \mathcal{O}_{\mathfrak{p}} の単数 u が存在して a=\pi_{K_{\mathfrak{p}}}^n u と表せる。以上のことから \mathcal{O}_{\mathfrak{p}} の単数群を U_{K_{\mathfrak{p}}} と書けば

K_{\mathfrak{p}}^* = \langle \pi_{K_{\mathfrak{p}}} \rangle \times U_{K_{\mathfrak{p}}}

が分かる。ここで \langle \pi_{K_{\mathfrak{p}}} \rangle とは \pi_{K_{\mathfrak{p}}}で生成される巡回群である。

 

 

局所類体論の存在定理

いよいよ局所類体論の存在定理の正確な主張を確認する。

この節では K と書いたら付値 v による局所体とし、

\mathcal{O}_K = \{ a \in K \mid v(a) \geq 0 \}

\mathfrak{p} = \{ a \in K \mid v(a) \gt 0 \} = (\pi_{K})

U_{K} = \mathcal{O}_{K}^*

とする。また局所体上の有限次拡大体もまた局所体であることが知られているので、その有限次拡大体に対しても添え字の K の部分を入れ替えることで同様の記号を使う。

 

 

Galois拡大 L/K に対しそのノルムを

N_{L/K}(a) = \prod_{\sigma \in G(L/K)} \sigma (a)

により定める。

 

局所類体論の存在定理
K 上の有限次Abel拡大 L に対して
L \mapsto \mathcal{N}_{L} = N_{L/K} L^*
という対応は K 上の有限次Abel拡大から K^* の指数有限開部分群への1対1対応を与える。
またこの対応は
L_1 \supset L_2 \iff \mathcal{N}_{L_1} \subset \mathcal{N}_{L_2}
\mathcal{N}_{L_1} \cap \mathcal{N}_{L_2} = \mathcal{N}_{L_1L_2}
などの規則を満たす。
この時 K^* の指数有限開部分群 \mathcal{N}_{L} に対応する K 上の有限次Abel拡大体 L を \mathcal{N}_L に対応する類体という。

 

これにより「K 上のAbel拡大体を含む適当な体を見つける」という問題は「どんなノルム群にも含まれるような K^* の適当な指数有限開部分群を見つける」というように位相的にも群論的にも考察できるより簡単な対象へと問題を書き換えることができるのである。

 

よって以降 K^* の部分群について調べる。

U_{K}^{(n)} = 1 + \mathfrak{p}^n

とすればこれは1の基本近傍系（つまりどんな1の開近傍も十分大きい n が存在して U_K^{(n)} を含む）となる。よって任意の K 上有限次Abel拡大体 L/K に対し十分大きい n が存在し

U_{K}^{(n)} \subset N_{L/K} L^*

となる。

十分大きい n をとればこれが成り立つわけだが、そのような n の内最小のものは L に関する情報を持っている。

 

定理
U_{K}^{(n)} \subset N_{L/K} L^* となる最小の n が0であることと L/K が不分岐なことは同値である。

 

以上より N_{L/K}L^* の部分群として U_{K}^{(n)} が持ってこれることが分かったが K^* = \langle \pi_K \rangle \times U_K であったことから U_{K}^{(n)} は K^* 内で指数有限にはならいないのである。よって対応する類体を考えるには \langle \pi_K \rangle 分の自由度を潰したい。ここで、 N_{L/K}(\pi_{L}) の素イデアル分解を考えれば次の定理が分かる。

 
定理
ある整数 f （これは相対次数となる）が存在して
(N_{L/K}(\pi_L))=(\pi_K^{f})
が成り立つ。
 
以上より任意の有限次Abel拡大 L/K に対して整数 n,f が存在して
N_{L/K}L^* \supset \ \langle \pi_K^f \rangle \times U_K^{(n)}
が成り立つことが分かった。
よって局所類体論の存在定理より局所体版のKronecker-Weberの定理を示すには \langle \pi_K^f \rangle \times U_K^{(n)} に対応する類体 M_{n,k} を構成すればいいことが分かる。
さらに局所類体論の存在定理を使えば
\langle \pi_K^f \rangle \times U_K^{(n)} =  (\langle \pi_K^f \rangle \times U_K) \cap  (\langle \pi_K \rangle \times U_K^{(n)})
であることから \langle \pi_K^f \rangle \times U_K と \langle \pi_K \rangle \times U_K^{(n)} に対応する類体を M_f, M_n とすれば 
M_{f,n} = M_f M_n
であるので M_f と M_n を構成すればいい。
 
まず M_f について。
対応する類体の定義より
N_{L/K}M_f^* = \langle \pi_K^f \rangle \times U_K \supset U_K = U_{K}^{(0)}
であるので M_f/K は不分岐拡大である。さらにN_{L/K}M_f^* は K^* 内で指数 f の部分群であるので \lbrack M_f : K \rbrack = f である。
よって K 上 f 次の不分岐拡大を具体的に構成したい。このとき次の定理が存在する。
 
定理
( \mathcal{O} : \mathfrak{p} ) = q とする。任意の整数 f に対して \zeta_{q^f -1} を1の原始 q^f -1 乗根とすれば K(\zeta_{q^f -1})/K は f 次の不分岐拡大である。
 
つまり M_f = K(\zeta_{q^f -1}) と具体的に構成することができた。
 
M_n について。
K=\mathbb{Q}_p の時はノルム群が比較的簡単に計算できる。
 
定理
L=\mathbb{Q}_p(\zeta_{p^n}) とする。なら
N_{L/ \mathbb{Q}_p} L^* = \langle \pi_K \rangle \times U_K^{(n)}
が成り立つ。
 
よって K = \mathbb{Q}_p のときは M_n = \mathbb{Q}_p(\zeta_{p^n}) と構成できる。
 
以上から p-進数版のKronecker-Weberの定理を得る。
 
p-進数版のKronecker-Weberの定理
任意の \mathbb{Q}_p 上有限次Abel拡大は、ある整数 f,n が存在して \mathbb{Q}_p(\zeta_{p^n(p^f -1)}) に含まれる。
 
 

最後に

では一般の局所体上へこの定理を一般化できるだろうか？
上の議論よりあとは M_n を具体的に構成できれば良いのだが、そのためにはノルム群についてさらに詳しく調べる必要がある。ここで実は類体論には相互法則という強力な武器が存在するのである。
次回ではそんな局所類体論の相互法則を紹介することで一般の局所体へとKronecker-Weberの定理を一般化する。
 
 
（次回は近日公開予定）
 

 

参考文献

J.Neukirch, Algebraic Number Theory, Springer

link.springer.com

 

雪江 明彦, 整数論2 代数的整数論の基礎, 日本評論社

www.nippyo.co.jp

 

*1:正確にはこれは相互法則であるが今回は類体論の使い方を見ることがメインなので簡単のため存在定理に入れることとする。

平方剰余の相互法則のGauss周期による証明

本記事は日曜数学 Advent Calendar 202312日目の記事です。

昨日はキグロさんによる "書籍『笑わない数学』裏話" でした。

 

 

今回のテーマは平方剰余の相互法則である。

 

まず平方剰余とはなにかについて説明しよう。

定義 （平方剰余）
p を奇素数とする。
p と互いに素な整数 a に対して x^2 = a \mod pとなるような整数 x が存在するとき a は p を法として平方剰余であるといい、そうでない場合は a は p を法として平方非剰余であるという。
 
ここでうまくこの平方剰余性を表すことのできる関数を次で定める。
 
定義（Legendre記号）
以下で定める関数をLegendre記号という。
\left(\frac{a}{p}\right) =\begin{cases}1 \hspace{1.75em} (a\text{が}\bmod p\text{で平方剰余}) \\-1 \hspace{1em} (a\text{が}\bmod p\text{で平方非剰余})\end{cases}
 
ここでLegendre記号は
\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \mod p. 
という表示を持つことが知られている。よって
\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)
が成り立つことが分かる。
 
以上をもとに今回の主役である平方剰余の相互法則を紹介する。
 
平方剰余の相互法則
p,q を異なる奇素数とすれば
\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)
が成り立つ。
 
 
平方剰余の相互法則を示すには
\left(\frac{q}{p}\right)=\left(\frac{(-1)^{\frac{p-1}{2}}p}{q}\right)
を示せばよい。なぜならこれが正しければ、上に書いた定理から
\left(\frac{q}{p}\right)=\left(\frac{(-1)^{\frac{p-1}{2}}}{q}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right)
より平方剰余の相互法則が得られるからである。
 
 
今回はGauss周期と呼ばれる 1 の冪乗根の線形和で定義される数を用いた鮮やかで面白い証明方法を紹介する。さらに最後にこの証明に用いられていたテクニックからGaussがいかに時代を先駆けていたかについてを語る。
 

Gauss周期の定義と性質

整数 a に対しそれを奇素数 p を法として考えるとき、 \overline{a} とかくとする。このとき、p を法とした世界 \mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}=\{\overline{0},\overline{1},\cdots \overline{p-1}\} の \overline{0} 以外の集合 \mathbb{F}_p^* はある整数 g により生成される。つまり

\mathbb{F}_p^*=\{1,\overline{g},\overline{g}^2,\cdots,\overline{g}^{p-2}\}

とできる。この時 p-1 の約数 d に対して

H_d=\{1,\overline{g}^d,\overline{g}^{2d},\cdots\overline{g}^{(\frac{p-1}{d}-1)d}\}

と定める。これはつまり H_d=\mathbb{F}_p^{*d} としているのである。

例えば d=2 の時を考えると

H_2=\{1,\overline{g}^2,\overline{g}^{4},\cdots,\overline{g}^{p-3}\} , \overline{g}H_2=\{\overline{g},\overline{g}^3,\overline{g}^{5},\cdots,\overline{g}^{p-2}\}であるので H_2 \cap \overline{g}H_2 = \emptyset でさらに

\mathbb{F}_p^*=H_2 \cup \overline{g}H_2

と分かる。

 

 \zeta = e^{\frac{2\pi i}{p}} = \cos\frac{2\pi}{p} + i\sin\frac{2\pi}{p} とする。

この時次のようにGauss周期を定める。

定義（Gauss周期）
整数 a と p-1 の約数 d に対して
\lbrack a \rbrack_d = \sum\limits_{\beta\in H_d} \zeta^{\overline{a}\beta}
により定めたものを d 次のGauss周期という。
ただし、\gamma\in\mathbb{F}_p に対し \zeta^{\gamma} とは \gamma の適当な代表元 c\in\mathbb{Z} に対して \zeta^{c} と定めるとする。これは \zeta が 1 の p 乗根であることから定義可能である。

 

ここでGauss周期は

a^{-1}b \in H_d \iff \lbrack a \rbrack_d = \lbrack b \rbrack_d

を満たす。よって

\mathbb{F}_p^*=H_2 \cup \overline{g}H_2

であったことから、2次のGauss周期は \lbrack 1 \rbrack_2 と \lbrack g \rbrack_2 と \lbrack 0 \rbrack_2 のみであることが分かる。

よって、a\in H_2 は定義より a が p を法として平方剰余であることと同値なので \lbrack 1 \rbrack_2 = \lbrack a \rbrack_2 となることは a が p を法として平方剰余であることと同値である。また、 a が p を法として平方非剰余であることは \lbrack g \rbrack_2 = \lbrack a \rbrack_2 となることと同値であることも分かる。

以上より a が p を法として平方剰余であるかどうかという問題は \lbrack 1 \rbrack_2 = \lbrack a \rbrack_2 かどうかというGauss周期の言葉に書き換えることができた。

 

ここからは 2次のGauss周期の満たす性質について紹介する。

 

まずは

1 + \zeta + \zeta^2 + \cdots + \zeta^{p-1} = 0

という関係式を用いれば

\lbrack 1 \rbrack_2 + \lbrack g \rbrack_2 = -1

と分かる。

 

また、次の定理が知られている。

定理
q を p と異なる素数とすると q の倍数 a,b が存在して
(\lbrack 1 \rbrack_2)^q - \lbrack q \rbrack_2 = a + b\lbrack 1 \rbrack_2
と表せる。

 

次の定理は非常に重要で特に面白い定理である。（面白さの理由は最後の節にて解説する。）

定理（2次のGauss周期の基本定理）
方程式
\varphi_2(x) = x^2 + x - \frac{(-1)^{\frac{p-1}{2}}p-1}{4}
は \lbrack 1 \rbrack_2 と \lbrack g \rbrack_2 を解に持つ。

 

この定理より \lbrack1\rbrack_2 を解に持つような多項式は \varphi_2(x) で割り切れることもわかる。

 

今回は基本的に証明を省略したが、どれもGauss周期の性質を存分に使った証明であり面白いので是非参考文献の本を参照してほしい。

 

平方剰余の相互法則の証明

いよいよ平方剰余の相互法則の証明に入る。
まず示すべき主張を再確認する。
 
平方剰余の相互法則
p,q を異なる奇素数とすれば
\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right).
が成り立つ。
 
またこれを示すためには
\left(\frac{q}{p}\right)=\left(\frac{(-1)^{\frac{p-1}{2}}p}{q}\right)
を示せばよいのであった。
これを前節を用いてGauss周期の言葉で翻訳すると p を法として q が平方剰余であることと \lbrack q \rbrack_2=\lbrack 1 \rbrack_2 は同値であり、さらにq が平方非剰余であることと \lbrack q \rbrack_2=\lbrack g \rbrack_2 は同値になるので
\lbrack q \rbrack_2=\lbrack 1 \rbrack_2 \Longrightarrow \left(\frac{(-1)^{\frac{p-1}{2}}p}{q}\right) = 1
と
\lbrack q \rbrack_2=\lbrack g \rbrack_2 \Longrightarrow \left(\frac{(-1)^{\frac{p-1}{2}}p}{q}\right) = -1
の二つが示されれば良いことが分かる。
 
証明：
\lbrack q \rbrack_2=\lbrack 1 \rbrack_2とする。なら前節から q の倍数である整数 a,b により
(\lbrack 1 \rbrack_2)^q - \lbrack q \rbrack_2 = (\lbrack 1 \rbrack_2)^{q} - \lbrack 1 \rbrack_2 = a + b\lbrack 1 \rbrack_2
と書ける。よって
f(x) = x^q - x - (a + bx)
は \lbrack 1 \rbrack_2 を解としてもつ方程式である。したがって2次Gauss周期の基本定理より f(x) は
\varphi_2(x) = x^2 + x - \frac{(-1)^{\frac{p-1}{2}}p-1}{4}
で割り切れることが分かる。
ここでこれらの方程式の各係数達を q を法として考える。多項式 s(x) の各係数を q を法として考えたものを \overline{s}(x) とかく。整数にも同じ表記を用いる。すると a,b が q の倍数であったことから
\overline{f}(x) = x^q -x
が \overline{\varphi_2}(x) で割り切れるという風に言い換えられる。ここで \overline{f}(x) の解は高々 q 個であることから、Fermatの小定理よりその解は \mathbb{F}_q のすべての元でありそれらで尽くされることが分かる。特に \overline{\varphi_2}(x) の解も \mathbb{F}_q の元と分かる。今解の公式から \overline{\varphi_2}(x) の解は \overline{2}^{-1}(-\overline{1}\pm\sqrt{(\overline{-1})^{\frac{p-1}{2}}\overline{p}}) であり、 q が p と異なる奇素数なことに注意すれば
\sqrt{(\overline{-1})^{\frac{p-1}{2}}\overline{p}}\in\mathbb{F}_q^*
と分かる。よって (-1)^{\frac{p-1}{2}}p は q を法として平方剰余である。
次に \lbrack q \rbrack_2=\lbrack g \rbrack_2 とする。なら \lbrack 1 \rbrack_2 + \lbrack g \rbrack_2 = -1 よりある q の倍数 a,b によって
(\lbrack 1 \rbrack_2)^q - \lbrack q \rbrack_2 = (\lbrack 1 \rbrack_2)^{q} - (-1 - \lbrack 1 \rbrack_2) = a + b\lbrack 1 \rbrack_2
と表せる。よって
h(x)= x^q + x + 1 -(a + bx)
と置くとこれは \lbrack 1 \rbrack_2 を解に持つので \varphi_2(x) で割り切れる。同様にこれらの多項式を q を法として考えると
\overline{h}(x) = x^q + x +\overline{1}
である。もし \overline{\varphi_2}(x) が \mathbb{F}_q 上に解を持つとしてそれを \alpha とすれば
\alpha^q + \alpha + 1 = 0
を満たすのでFermatの小定理から \alpha^q = \alpha となり
2\alpha+1=0
となる。よって \alpha = \overline{2}^{-1}(\overline{-1}) である。一方で \overline{\varphi_2}(x) の解を解の公式より計算すると \overline{2}^{-1}(\overline{-1} \pm \sqrt{(\overline{-1})^{\frac{p-1}{2}}\overline{p}}) であるので (\overline{-1})^{\frac{p-1}{2}}\overline{p} = \overline{0} を得るが p と l は異なる素数であったのでこれは矛盾。よって \varphi_2(x) は \mathbb{F}_q 上に解を持たない。 つまり  \sqrt{(\overline{-1})^{\frac{p-1}{2}}\overline{p}}\not\in\mathbb{F}_q であるので (-1)^{\frac{p-1}{2}}p は q を法として平方非剰余である。
(証明終)
 

現代数学から見たGaussの証明

さて、今回の証明の鍵となったポイントは次の2点である。

Point 1. 2次のGauss周期の基本定理。
Point 2. 有限体 \mathbb{F}_q でのGauss周期の値について考察する。
ここでそれぞれの考察を現代数学における視点から見てみよう。
Point 1.
まず驚くべきは平方剰余に関する問題を解くときに1の冪乗根に注目するという点である。詳しく言うと我々は今 \sqrt{(-1)^{\frac{p-1}{2}}p} が有限体 \mathbb{F}_q に含まれているかどうかという議論をする為に　\sqrt{(-1)^{\frac{p-1}{2}}p} を1の冪乗根の線形和であるGauss周期を用いて書き考察をしたのだが、「平方根が1の冪乗根達の線形和で書ける」という事実が驚きである。
この驚きの事実は現代ではKronecker-Weberの定理というより一般化された姿として知られている。
 
定理（Kronecker-Weberの定理）
任意の \mathbb{Q} 上有限次Abel拡大は円分体の部分体である。
 
ここで整数 m に対して \mathbb{Q}(\sqrt{m})/\mathbb{Q} は有限次Abel拡大なので、ある n が存在して \mathbb{Q}(\zeta_n) に含まれる。よって \sqrt{m} は \zeta_n 達の線形和で書けるのである。
 
Point 2.

次に注目すべきは方程式 \overline{f}(x)=x^q-x である。今回の証明ではGauss周期が \overline{f}(x) の解であることからそれが \mathbb{F}_q の元であることを示したのであった。このテクニックは現代ではGaloisの基本定理として説明ができる。実際、 \alpha \in \mathbb{Z}\lbrack\zeta\rbrack として q の上にある \mathbb{Z}\lbrack\zeta\rbrack の素イデアル \mathfrak{Q} をとる。ここでは \mathbb{Z}\lbrack\zeta\rbrack の元に対して \mathfrak{Q} を法として考えるときに上線をつけるとする。ここで \overline{f}(\overline{\alpha})=0 が成り立つのなら

\overline{\alpha}^q=\overline{\alpha}

となる。これは \kappa(\mathfrak{Q}) = \mathbb{Z}\lbrack \zeta \rbrack / \mathfrak{Q} と \kappa(q) = \mathbb{F}_q と書けば  \overline{\alpha} は \mathrm{Gal}(\kappa(\mathfrak{Q})/\kappa(q)) の生成元であるFrobenius写像において不変であるということを意味する。よってGaloisの基本定理より \overline{\alpha} \in \mathbb{F}_q であることが分かるのである。

 

 

これらのようにGaussは後に美しい理論として整理されるようなテクニックを証明で幾つか用いているのである。また、さらにGaussが幾つもの証明を与えるほどに考察をしていたこの平方剰余の一般化に関する議論はKummerによる理想数の発想を産み、そして類体論と呼ばれる美しい理論によって描かれることとなった。

このアイディアに溢れ、時代を先駆けたGaussの証明の美しさが伝われば幸いである。

 

参考文献

栗原将人, 「ガウスの数論世界をゆく」, 数学書房

www.sugakushobo.co.jp