インテジャーズ

インテジャーズ

数、特に整数に関する記事。

平方剰余の相互法則

1という数を聴いて最初に次の合同式が思い浮かぶ人はまずいないでしょう。私も思い浮かべません(笑)。でも、一応1という数が特徴的に現れる公式ではあります。

nが3の倍数でなければ、n^2 \equiv 1 \pmod{3}が成り立つ。

3の倍数は二乗しても3の倍数です。つまり、平方数を3で割った余りは絶対に2になりません。このことはいくつかの問題を解く際に非常に便利な事実です。証明はとても簡単です。3で割った余りは0, 1, 2のいずれかですが、これらは2乗すると0, 1, 4となります。すなわち、4 \equiv 1 \pmod{3}という合同が証明の全てです。

さて、話を一気に一般化して平方剰余および平方非剰余という言葉を導入しましょう(話を簡単にするため、法は奇素数の場合だけ扱います)。

定義 pを奇素数とし、apと素な整数とする。このとき、aが(pを法とする)平方剰余であるとは、ある整数xが存在してx^2 \equiv a \pmod{p}が成り立つときに言う。逆に、このようなxが存在しないとき、a平方非剰余とよばれる。

冒頭の話は3を法として考えたときに、1は平方剰余、2は平方非剰余になるという話でした。これらの話を扱いやすくするためにLegendre記号を導入しましょう:

Legendre記号 apを法として平方剰余であるときには\displaystyle \left( \frac{a}{p} \right) =1、平方非剰余であるときには\displaystyle \left( \frac{a}{p} \right) =-1として記号\displaystyle \left( \frac{a}{p} \right)を定義する。

a \equiv b \pmod{p}ならば\displaystyle \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right)なので、Legendre記号は写像

\displaystyle \left( \frac{}{p} \right) \colon \mathbb{F}_p^{\times} \longrightarrow \{ \pm 1\}

と思えます。

冒頭の式は応用が多く(実際、今後の記事において応用することになります)、他のpでもこのような議論ができるようにするために与えられたaに対して\displaystyle \left( \frac{a}{p} \right)の計算方法を確立することが今回の記事の目標です。冒頭のように1, \dots, p-1を全て二乗して\bmod{p}計算すれば一応目的は達成できます。しかしながら、考えているaについてのみ平方剰余か平方非剰余かを判定したい場合にはpが大きいと非効率です。もっと効率的な方法が存在します。与えられたaについてのみ判定する方法として、Eulerの規準という方法が存在します:

Eulerの規準 合同式
\displaystyle \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p}
が成立する。

これから、写像\displaystyle \left( \frac{}{p} \right) \colon \mathbb{F}_p^{\times} \longrightarrow \{ \pm 1\}は群凖同型であることがわかります。Eulerの規準は重要ですが、効率的ではありません。それはa^{\frac{p-1}{2}}の計算が大変だからです。実はもっと効率的な計算法が存在します。次の3つの定理がその計算方法を与えています(つまり、今回の記事の到達点です):

第一補充則 \displaystyle \ \ \ \ \ \ \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}.

第二補充則 \displaystyle \ \ \ \ \ \ \left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}.

平方剰余の相互法則 p, qを相異なる奇素数とする。このとき、
\displaystyle \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}
が成り立つ。

Legendre記号の準同型性および素因数分解を考えることにより\displaystyle \left( \frac{-1}{p} \right), \left( \frac{2}{p} \right)およびp未満の奇素数qについて\displaystyle \left( \frac{q}{p} \right)が計算できれば十分であることに注意しましょう。最初の2つが第一補充則および第二補充則により計算できます。\displaystyle \left( \frac{q}{p} \right)は一度に計算されるのではなく、平方剰余の相互法則によって法pの問題を法qの問題に帰着します。 q < pなので高々有限回の操作で計算が終了します。計算例を見てみましょう:

20151207が法46398467で平方剰余であることを証明します*1

\displaystyle \left( \frac{20151207}{46398467} \right) = \left( \frac{3^3\times 149\times 5009}{46398467} \right) = \left( \frac{3}{46398467} \right) \left( \frac{149}{46398467} \right) \left( \frac{5009}{46398467} \right),

\begin{align} \left( \frac{3}{46398467} \right) &= -\left( \frac{46398467}{3} \right) =-\left( \frac{2}{3} \right) = -(-1)^{\frac{3^2-1}{8}} = 1,\\
\left( \frac{149}{46398467} \right) &= \left( \frac{46398467}{149} \right) = \left( \frac{16}{149} \right) = \left( \frac{4}{149} \right)^2 = 1,\\
\left( \frac{5009}{46398467} \right) &= \left( \frac{46398467}{5009} \right) = \left( \frac{100}{5009} \right) = \left( \frac{10}{5009} \right)^2 = 1 \end{align}

となって、

\displaystyle \left( \frac{20151207}{46398467} \right)=1

が証明されました。すなわち、合同式 x^2 \equiv 20151207 \pmod{46398467}の解が存在することがわかりました(解が何かはわからないにもかかわらず!)。

如何に平方剰余の相互法則が強力な定理かが伝わったことと思います。今、この文をパソコンで記述している際、「強力」が「協力」と最初に変換されたのですが、実は「協力」でも正しいのです!つまり、平方剰余の相互法則は素数pと素数qが協力し合っている法則と思うことができるのです。我々は計算の手段として追い求めた法則が、実はかように対称的で美しい法則であることを知って言葉を失うのです。素数は孤独ではない!

では、証明されていない定理達に証明を与えていきましょう。まず、次の「原始根の存在定理」が必要となります:

原始根の存在定理 pを素数とする。このとき、乗法群\mathbb{F}_p^{\times}は巡回群である。生成元の代表元のことを法p原始根とよぶ。

補題1 Gをアーベル群、a, bを互いに素な自然数、g, h\in Gをそれぞれ位数a, bなる元とする。このとき、ghの位数はabである。

証明. Gはアーベル群なので、(gh)^{ab}=(g^a)^b(h^b)^a=1が成り立つ。よってghの位数はabの約数である。a, bは互いに素なので、素因数分解の一意性からghの位数はaの約数a_1, bの約数b_1を用いてa_1b_1と表すことができる。このとき、最初の計算と同様にg^{a_1b_1}h^{a_1b_1}=1が成り立つ。この式の両辺をa_2:=a/a_1乗すると(g^a)^{b_1}h^{ab_1}=1を得る。g^a=1であるから、h^{ab_1}=1。よって、hの位数bab_1を割り切る。baは互いに素なのでbb_1を割り切る。これはb=b_1を意味する。同様にa=a_1となってa_1b_1=ab、すなわちghの位数はabであることが示された。 Q.E.D.

補題2 体係数多項式の根の個数は高々次数個である。

証明. 因数定理を使えば、数学的帰納法によって証明できる。 Q.E.D.

補題3 pを素数、dp-1の約数とする。このとき、x^{d}-1\in \mathbb{F}_p[x] \mathbb{F}_pにちょうどd個の根をもつ。

証明. x^{p-1}-1がちょうどp-1個の根を\mathbb{F}_pにもつことは、すなわちFermatの小定理である。dp-1の約数であるとき、x^{p-1}-1=(x^d-1)f(x)と因数分解される。このとき、補題2によってx^d-1は高々d個の根を\mathbb{F}_pにもち、f(x)は高々p-1-d個の根を\mathbb{F}_pにもつ。しかしながら、x^{p-1}-1の根の個数がp-1個であるという事実を実現するためには、x^d-1およびf(x)は実際にd個およびp-1-d個の根をもっていなければならない。 Q.E.D.

原始根の存在定理の証明. p=2のときは自明なので、pを以下奇素数とする。\displaystyle p-1=\prod_{\ell}\ell^{e_{\ell}}と素因数分解する(e_{\ell}\geq 1)。このとき、\ell^{e_{\ell}}p-1の約数なのでx^{\ell^{e_{\ell}}}-1\mathbb{F}_pにちょうど\ell^{e_{\ell}}個の根をもつ。また、\ell^{e_{\ell}-1}p-1の約数なのでx^{\ell^{e_{\ell}-1}}-1\mathbb{F}_pにちょうど\ell^{e_{\ell}-1}個の根をもつ。よって、\mathbb{F}_pは位数\ell^{e_{\ell}}の元を\ell^{e_{\ell}-1}(\ell -1)個もつことがわかる。特に、少なくとも1つは存在する。1つとって、a_{\ell}としよう。このとき、\displaystyle a:=\prod_{\ell}a_{\ell}とすれば、補題1よりaは位数p-1であることがわかる。 Q.E.D.

Eulerの規準の証明. rを法pの原始根としよう。a \equiv r^k \pmod{p}なる整数kが存在する。このとき、aが平方剰余であることはr^{2j} \equiv r^k \pmod{p}なる整数jが存在することと同値であり、それはすなわちkが偶数であること同値である。一方、a^{\frac{p-1}{2}} \equiv (r^{\frac{p-1}{2}})^k = (-1)^kである(r^{p-1} \equiv 1 \pmod{p}なのでr^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}。もし、r^{\frac{p-1}{2}} \equiv 1\pmod{p}ならばrが原始根であるという仮定に反する)。 Q.E.D.

第一補充則の証明. これはEulerの規準の直接の系である。 Q.E.D.

Eulerの規準は非効率と述べましたが、|a|=1のときに限れば効率的というわけです。以下、第二補充則および平方剰余の相互法則を証明しますが、証明はたくさんあります。ここではGauss和による証明法を採用します。これは最もシンプルな証明というわけではありませんが、

  1. 十分シンプルである
  2. Gauss和はこの証明に限らず重要な対象である
  3. 何か重要な量を二通りの方法で計算すると非自明な結果が得られるというタイプの証明の良い例である。

という理由でこれを選びました。

第二補充則の証明. \zeta_8 := e^{\frac{2\pi i}{8}}とおき(1の原始8乗根)、\tau := \zeta_8+\zeta_8^{-1}とおく(この証明における主役)。このとき、\tau^2 = \zeta_8^2+2+\zeta_8^{-2}=i+2-i=2が成り立つ。\tau^pを二通りの方法で計算する。以下、合同式は\mathbb{Z}[ \zeta_8 ] で考える。
まず、Eulerの規準により

\displaystyle \tau^{p} = (\tau^2)^{\frac{p-1}{2}}\tau = 2^{\frac{p-1}{2}} \tau \equiv \left( \frac{2}{p} \right) \tau \pmod{p}

と計算できる。一方、\tau^p \equiv \zeta_8^p + \zeta_8^{-p} \pmod{p}なので、

\displaystyle \tau^p \equiv \begin{cases} \zeta_8+\zeta^{-1} & p \equiv \pm 1 \pmod{8} \\ -\zeta_8-\zeta_8^{-1} & p \equiv \pm 3 \pmod{p} \end{cases} = (-1)^{\frac{p^2-1}{8}}\tau

を得る。2つの計算を比較して両辺に\tauを掛けることによって\displaystyle 2\left( \frac{2}{p} \right) \equiv 2(-1)^{\frac{p^2-1}{8}} \pmod{p}が示された。pは奇素数なので、これは第二補充則を意味する。 Q.E.D.

p^{\ast} := (-1)^{\frac{p-1}{2}}pと定義します。このとき、第一補充則を用いると平方剰余の相互法則は\displaystyle \left( \frac{p^{\ast}}{q} \right) = \left( \frac{q}{p} \right)と同値であることがわかります。\zeta_p := e^{\frac{2\pi i}{p}}とします。

Gauss和 \displaystyle \mathcal{G} := \sum_{a=1}^{p-1} \left( \frac{a}{p} \right) \zeta_p^a.  捩れGauss和 \displaystyle \mathcal{G}_b := \sum_{a=1}^{p-1} \left( \frac{b}{p} \right) \zeta_p^{ab}, (b \in \mathbb{F}_p^{\times}).

証明のKeyは \displaystyle \widehat{\mathcal{G}} := \sum_{b=1}^{p-1}\mathcal{G}_b^2 を二通りの方法で計算することです。

apの倍数であるときは\displaystyle \left( \frac{a}{p} \right) = 0とLegendre記号の定義を拡張します(これは\displaystyle \left( \frac{a}{p} \right)をDirichlet指標と考えると自然な拡張です)。このとき、\displaystyle \mathcal{G} = \sum_{a=0}^{p-1} \left( \frac{a}{p} \right) \zeta_p^aであり、\displaystyle \mathcal{G}_0 := \sum_{a=1}^{p-1}\left( \frac{a}{p} \right) = 0なので、\displaystyle \widehat{\mathcal{G}} = \sum_{b=0}^{p-1}\mathcal{G}_b^2となります(\mathcal{G}_0=01, \dots, p-1のうち半分が平方剰余で半分が平方非剰余であることからわかります*2 )。

補題4 apと互いに素ならば\displaystyle \sum_{b=0}^{p-1}\zeta_p^{ab} = 0.

証明. \displaystyle \sum_{b=0}^{p-1}\zeta_p^{ab} = \sum_{b=0}^{p-1}(e^{\frac{2\pi i}{p}a})^b = \frac{e^{2\pi i a}-1}{e^{2\pi ia/p}-1} = 0. Q.E.D.

定理  \ \ \ \ \ \ \mathcal{G}^2 = p^{\ast}.

証明. b \in \mathbb{F}_p^{\times}に対して

\displaystyle \mathcal{G}_b = \left( \frac{b}{p} \right)^{-1}\sum_{a=1}^{p-1}\left( \frac{ab}{p} \right) \zeta_p^{ab} = \left( \frac{b}{p} \right)^{-1} \mathcal{G}

が成り立つので、

\displaystyle \widehat{\mathcal{G}} = \sum_{b=1}^{p-1}\left( \frac{b}{p} \right)^{-2}\mathcal{G}^2 = \mathcal{G}^2\sum_{b=1}^{p-1} = (p-1)\mathcal{G}^2

と計算できる。一方、定義から

\displaystyle \begin{equation}\begin{split}
\widehat{\mathcal{G}} &= \sum_{b=0}^{p-1}\left( \sum_{a_1=0}^{p-1}\left( \frac{a_1}{p} \right) \zeta_p^{a_1b} \right) \left( \sum_{a_2=0}^{p-1}\left( \frac{a_2}{p} \right) \zeta_p^{a_2b} \right) \\
&= \sum_{b=0}^{p-1}\left( \sum_{a_1, a_2=0}^{p-1}\left( \frac{a_1}{p} \right) \left( \frac{a_2}{p} \right) \zeta_p^{(a_1+a_2)b} \right) \\
&=\sum_{a_1, a_2 = 0}^{p-1}\left( \frac{a_1a_2}{p} \right) \sum_{b=0}^{p-1}\zeta_p^{(a_1+a_2)b}\end{split}\end{equation}

と変形できる。補題4より最後の和はa_1+a_2 \equiv 0\pmod{p}のときしか生き残らない。よって、

\displaystyle \widehat{\mathcal{G}} = \sum_{a=0}^{p-1}\left( \frac{-a^2}{p} \right) p = (p-1)p^{\ast}

を得る(第一補充則を用いた)。以上、二通りの計算を比較することにより、(p-1)\mathcal{G}^2=(p-1)p^{\ast}、すなわち\mathcal{G}^2=p^{\ast}が示された。 Q.E.D.

これより、\mathbb{Q}(\mathcal{G}) \subset \mathbb{Q}(\zeta_p)がわかります。いずれKronecker-Weberの定理やKroneckerの青春の夢について記事を書こうと思います。また、Gauss和の符号の決定はGaussにとっても難しい問題だったようです(相互法則の証明においてはGauss和は触媒のようなものであって、符号の決定までは必要ない)。

平方剰余の相互法則の証明の完成. qpと異なる奇素数とします。Eulerの規準より

\displaystyle \mathcal{G}^q = (p^{\ast})^{\frac{q-1}{2}}\mathcal{G} \equiv \left( \frac{p^{\ast}}{q} \right) \mathcal{G} \pmod{q}

を得る(合同式は\mathbb{Z}[ \zeta_q ] で考える)。一方、

\displaystyle \mathcal{G}^q \equiv \sum_{a=1}^{p-1}\left( \frac{a}{p} \right) \zeta_p^{aq} = \left( \frac{q}{p} \right)^{-1} \mathcal{G} = \left( \frac{q}{p} \right) \mathcal{G} \pmod{q}.

従って、\mathcal{G}^qの二通りの計算を比較して両辺\mathcal{G}倍することにより、

\displaystyle \left( \frac{p^{\ast}}{q} \right) p^{\ast} \equiv \left( \frac{q}{p} \right) p^{\ast} \pmod{q}

を得る。pqは互いに素なので、\displaystyle \left( \frac{p^{\ast}}{q} \right) = \left( \frac{q}{p} \right)が示された。 Q.E.D.

*1:46398467は素数です。ちなみに、6398467, 398467, 98467, 8467, 467, 67, 7は全て素数です。このような素数についてはいずれ記事を書きます。 追記)書きました。 integers.hatenablog.com

*2:x^2 \equiv (-x)^2に注意すればわかる。