美的数学のすすめ

初等整数論のうち、平方剰余の相互法則の意味を当面の目標としたいと思います。ゆくゆくは、ガウス和、円分体論まで到達したいです。

平方剰余とルジャンドル記号

最終行の赤字部分を修正しました。2015/6/4

 前回まで、円分多項式\(\Phi_{q}\)の\(\bmod{p}\)での因数分解の法則が、\(p\)の\(\bmod{q}\)での位数と関連するというお話をしました。つまり、円分多項式の因数分解の法則は、modが入れ替わってしまいます。

 このように、modが入れ替わる代表例として、平方剰余の相互法則があります。

 平方剰余の相互法則については次回以降に解説するとして、今回は、平方剰余の相互法則を考える前提として、平方剰余とルジャンドル記号について説明します。

 平方剰余とは

 \(p\)を奇素数とするとき、\( (\mathbb{Z}/p\mathbb{Z})^{\times}\)の平方剰余(quadratic residue)とは、\( (\mathbb{Z}/p\mathbb{Z})^{\times}\)の原始根を\(r\)としたときに、\(r\)の偶数乗となる\( (\mathbb{Z}/p\mathbb{Z})^{\times}\)の元でした。そして、この定義は、原始根\(r\)の取り方に依りません。

 \( (\mathbb{Z}/p\mathbb{Z})^{\times}\)の元で平方剰余でないもの、つまり、原始根の奇数乗と表せるものを平方非剰余(quadratic nonresidue)といいます。

 このように、\( (\mathbb{Z}/p\mathbb{Z})^{\times}\)の平方剰余と平方非剰余を定義すると、この定義は、\(p\)と素な整数に拡張できます。

 \(a\)を\(p\)と素な整数とします。\(a\)を\(\bmod{p}\)すると\( (\mathbb{Z}/p\mathbb{Z})^{\times}\)の元になります。そこで、\(a\)を\(\bmod{p}\)したときに平方剰余となる場合、\(a\)は\(\bmod{p}\)で平方剰余(quadratic residue modulo p)といいます。また、同様に\(\bmod{p}\)で平方非剰余(quadratic residue nonmodulo p)も定義できます。

このとき、平方剰余の定義より次が成り立ちます。

\(a\)を\(p\)と素な整数とするとき、 \[a\text{は平方剰余}\Longleftrightarrow x^{2}\equiv a\pmod{p}\text{が解をもつ}\]

 これが、平方剰余の通常の定義です。平方剰余・平方非剰余の定義は、どこか不自然で人工的な感じを受けてしまいますが、整数を偶数と奇数とに分類するのが自然なのと同じように、\( (\mathbb{Z}/p\mathbb{Z})^{\times}\)を平方剰余と平方非剰余とに分類することは、自然で本質的な分類です。

ルジャンドル記号

 \(p\)と素な整数\(a\)に対し、記号\( \left(\frac{a}{p}\right)\)を、\(a\)が\(\bmod{p}\)で平方剰余のとき1、\(a\)が\(\bmod{p}\)で平方非剰余のとき-1とします。

 つまり、 \[ \left(\frac{a}{p}\right) = \begin{cases} 1 & (a\text{が}\bmod{p}\text{で平方剰余}) \\ -1 & (a\text{が}\bmod{p}\text{で平方非剰余}) \end{cases} \]

です。この記号をルジャンドル記号(Legendre symbol)といいます。

 ルジャンドル記号は、分数のような記号ですが必ずカッコが必要です。もちろん、分数とは何の関係もありません。

 ルジャンドル記号の定義より、

\[\left(\frac{np+a}{p}\right)=\left(\frac{a}{p}\right)\]

が成り立ちます。また、下記で示すとおり、乗法に関して

\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\] が成立します。そのため、この分数のような記号と、平方剰余とは、意外と相性がよいです。

ルジャンドル記号の成立 

オイラーの規準

 平方剰余を考える際に基本的な性質は、次のオイラーの規準です。

(オイラーの規準)
 \(a\)を素数\(p\)と素な整数とするとき \[\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}\]

 フェルマーの小定理より、\(a^{p-1}\equiv1\pmod{p}\)が成立します。そのため、\(a^{\frac{p-1}{2}}\equiv\pm1\pmod{p}\)となります。オイラーの規準は、この式の右辺がプラスの場合が平方剰余、マイナスの場合が平方非剰余となることを示しています。

 \( (\mathbb{Z}/p\mathbb{Z})^{\times}\)は位数\(p-1\)の巡回群であり、位数\(\frac{p-1}{2}\)の分部群を唯一もちます。その位数\(\frac{p-1}{2}\)の分部群\(H_{\frac{p-1}{2}}\)が平方剰余な元からなる部分群です。

 そして、一般的に、\(p-1\)の約数\(f\)に対して、位数\(f\)の分部群\(H_{f}\)は次のように特徴づけられます。

既約剰余類群の部分群 - 美的数学のすすめ

\[\begin{align} H_{f}&=\{r^{\frac{p-1}{f}m}\ \ (r\ \text{は原始根})\ |\ \ m:\text{整数}\ \ \} \\ &=\{n\in (\mathbb{Z}/p\mathbb{Z})^{\times}\ |\text{ある}x\in(\mathbb{Z}/p\mathbb{Z})^{\times}\text{が存在して}x^{\frac{p-1} {f}}=n \}\\ &=\{n\in (\mathbb{Z}/p\mathbb{Z})^{\times}\ |\ n^{f}=1\ \} \end{align}\]

ここで\(f=\frac{p-1}{2}\)とすれば、上のオイラーの規準が導かれます。

ルジャンドル記号の準同型性

 オイラーの規準から、ルジャンドル記号の次の性質が導かれます。

(ルジャンドル記号の準同型性)
\(a,b\)を\(p\)と素な整数とするとき

\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]

これは、ルジャンドル記号が、剰余類群 \( (\mathbb{Z}/p\mathbb{Z})^{\times}\)から\(\{\pm 1\}\)への群準同型であることを示しています。

第1補充法則

 オイラーの規準は、\(p\)と素なすべての整数\(a\)について成り立ちますので、\(a=-1\)でも成立しています。これにより次の第一補充法則が示せます。

(第一補充法則) \[ \left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}\]

これをもう少し具体的に書き下すと次のようになります。

\[\begin{align} &-1\text{が}\bmod{p}\text{で平方剰余}&\Longleftrightarrow p\equiv1\pmod{4}\\ &-1\text{が}\bmod{p}\text{で平方非剰余}&\Longleftrightarrow p\equiv 3\pmod{4} \end{align}\]

 これにより、合同式\(x^{2}=-1\pmod{p}\)が解ける条件が分かります。

\[\begin{align} &x^{2}=-1\pmod{p}\text{が}解あり&\Longleftrightarrow p\equiv 1\pmod{4}\\ &x^{2}=-1\pmod{p}\text{が}解なし&\Longleftrightarrow p\equiv 3\pmod{4} \end{align}\]

 ディリクレの算術級数定理より\(p\equiv 1\pmod{4}\)となる素数と\(p\equiv 3\pmod{4}\)となる素数は無限にあることが知られています。

 さらに、それぞれの素数は概ね同数ある(つまり、ある素数\(p\)を選んだときに、それが\(p\equiv 1\pmod{4}\)となるか\(p\equiv 3\pmod{4}\)となるかは、それぞれ2分の1の確率である。)ことが知られています。

 つまり、\(x^{2}\equiv -1\pmod{p}\)は、概ね半分の素数\(p\)で解があり、概ね半分の素数\(p\)で解がないことが分かります。

 sageで計算したところ、100までの素数(2は除く)24個のうち、\(p\equiv1\pmod{4}\)なる素数は11個、\(p\equiv3\pmod{4}\)なる素数は13個あることが分かります。さらに1000までの素数(2は除く)167個のうち、\(p\equiv1\pmod{4}\)なる素数は80個、\(p\equiv1\pmod{4}\)なる素数は87個あることが分かります。このように、\(n\)以下の素数(2は除く)で\(p\equiv1\pmod{4}\)なる素数の個数と\(p\equiv3\pmod{4}\)なる素数の個数を表に下のが次の表です。

\(n\)以下の素数 \(p\equiv1\pmod{4}\)なる素数の個数 \(p\equiv3\pmod{4}\)なる素数の個数
10 1 2
100 11 13
1000 80 87
10000 609 619
100000 4783 4808
1000000 39175 39322
10000000 332180 332398
100000000 2880504 2880950

 この表をみると、\(p\equiv1\pmod{4}\)なる素数の個数と\(p\equiv3\pmod{4}\)なる素数の個数は、だいたい同じ数であることが分かります。

 また、この表からは、「\(p\equiv1\pmod{4}\)なる素数の個数」<「\(p\equiv3\pmod{4}\)なる素数の個数」と予想できそうです。しかし、この予想は誤っています。この表になっている、100000000(一億)以下の素数に限定しても、「\(p\equiv1\pmod{4}\)なる素数の個数」と「\(p\equiv3\pmod{4}\)なる素数の個数」とは、何度も大小関係が逆転しています。しかも、この大小関係は、無限に交代することが証明されています。