Excel VBA 数学教室ではアフィリエイトプログラムを利用して商品を紹介しています。

補充法則と相互法則

定理 F11 を再掲します。

$p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]

一般の正負の整数 $n$ は、$q_1,\:q_2,\:,\cdots$ を奇素数、$s,\:t_1,\:t_2,\:\cdots$ を $0$ 以上の整数として
\[n=\pm\,2^sq_1^{t_1}q_2^{t_2}\cdots\]
のように表せるので、整数が平方剰余であるかどうかは

\[\left(\frac{n}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)^s\left(\frac{q_1}{p}\right)^{t_1}\left(\frac{q_2}{p}\right)^{t_2}\cdots\]
を計算して判定することができます。すなわち任意の整数について、素因数分解によって奇素因数 $q_i$ をすべて求めて
\[\left(\frac{-1}{p}\right),\:\left(\frac{2}{p}\right),\:\left(\frac{q_i}{p}\right)\]
を計算すれば、その整数の平方剰余/平方非剰余を判定することができるということです。

第1補充法則

$\displaystyle\left(\frac{-1}{p}\right)$ は前々回記事で扱ったオイラーの判定条件

$p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
\[\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\quad (\mathrm{mod}\:p)\]

において $a=-1$ とすればよいだけで、平方剰余の第1補充法則とよばれています:

【定理F13:平方剰余の第1補充法則】
$p$ を奇素数とするとき、
\[\left(\frac{-1}{p}\right)= (-1)^{\frac{p-1}{2}}\]

ここで $p$ を $4$ で割ったときの余り ($\mathrm{mod}\:4$) で分類すると、$p=4k+1$ あるいは $p=4k+3$ のいずれかになります($4k$ や $4k+2$ は偶数なので $p$ として不適)。それぞれの場合について上の第1補充法則に入れて計算してみると、
\[\left(\frac{-1}{p}\right)= (-1)^{2k}=1,\quad \left(\frac{-1}{p}\right)= (-1)^{2k+1}=-1\]
となるので、
\[x^2\equiv -1\quad (\mathrm{mod}\:p)\]
が解をもつのは、$p=4k+1$ の形の素数のときだけです。たとえば、
\[x^2\equiv -1\quad (\mathrm{mod}\:5)\]
すなわち
\[x^2\equiv 4\quad (\mathrm{mod}\:5)\]
は解をもつということです。実際に確認してみましょう。
\[1^2,\:2^2,\:3^2,\:4^2,\:5^2\]
を $5$ で割ってみると
\[1,\:4,\:,\:4,\:1,\:0\]
となって、確かに余り $4$ が現れています。すなわち
\[x\equiv 2,\:3\quad (\mathrm{mod}\:5)\]
が解となります。

第2補充法則

次は $a=2$ の場合です。これもオイラーの判定条件に当てはめて
\[\left(\frac{2}{p}\right)\equiv 2^{\frac{p-1}{2}}\quad (\mathrm{mod}\:p)\]
によって判定することもできますが、たとえば $p=17$ とすると
\[\left(\frac{2}{11}\right)\equiv 2^8\quad (\mathrm{mod}\:17)\]
を計算しなくてはならず、少し面倒です。右辺が $(-1)^t$ の形になっていれば、$t$ の偶奇によってすぐに平方剰余/非剰余を判定できます。そこで登場するのが次の平方剰余の第2補充法則です。

【定理F14:平方剰余の第2補充法則】
$p$ を奇素数とするとき、
\[\left(\frac{2}{p}\right)= (-1)^{\frac{p^2-1}{8}}\]

この定理の証明の準備として、前回記事で扱った ガウスの補題 を少し噛み砕いた表現に直しておきます(意味は同じです)。

$p$ が奇素数、$(a,\:p)=1$ であるとき、
\[1a,\:2a,\:3a,\:\cdots,\:\frac{p-1}{2}a\]を $p$ で割って余りを並べて、$p/2$ より大きな数が $t$ 個あるならば、
\[\left(\frac{a}{p}\right)=(-1)^t\]が成り立つ。

さらに $a=2$ とすると、$(2,\:p)=1$ なので

$p$ を奇素数とすると、
\[2,\:4,\:6,\:\cdots,\:p-3,\:p-1\]を $p$ で割って余りを並べて、$p/2$ より大きな数が $t$ 個あるならば、
\[\left(\frac{2}{p}\right)=(-1)^t\]が成り立つ。

第2補充法則の証明にはこの定理を用いますが、一般的な証明は少し難しいので、まずは $p=11$ として具体的に調べてみます。
\[2,\:4,\:6,\:8,\:10\]
を $11$ で割って余りを並べると、
\[2,\:4,\:6,\:8,\:10\tag{1}\]
というように同じ数が並びます。このなかに $p/2=5.5$ より大きな数は $3$ 個あるので、ガウスの補題により
\[\left(\frac{2}{11}\right)=(-1)^3=-1\]
となって、$x^2\equiv 2\:(\mathrm{mod}\:11)$ が解をもたないことがすぐにわかります。しかし後の一般的証明のために、この $t=3$ を別の方法で数えてみます。(1) になかで $p/2=5.5$ より大きな余りは
\[6,\:8,\:10\tag{2}\]
です。これらの数を $11$ から引くと
\[5,\:3,\:1\tag{3}\]
というように $5.5$ より小さな奇数が並びます。つまり $p/2=5.5$ より大きな数の個数は $5.5$ より小さな奇数の個数に等しくなります。これは
\[t\equiv 1+3+5\quad (\mathrm{mod}\:2)\]
のように表すこともできます。$\mathrm{mod}\:2$ で考えているので、これに偶数をいくつ足しても合同ですから、
\[t\equiv 1+2+3+4+5\quad (\mathrm{mod}\:2)\]
と書き換えることもできます。以上を踏まえて一般的な証明を記述します。

[定理F14の証明]
$2,\:4,\:6,\:\cdots,\:p-2,\:p-1$ を $11$ で割って余りを並べると、
\[2,\:4,\:6,\:\cdots,\:p-2,\:p-1\tag{4}\]
となります。このなかに $p/2$ より大きな数 $r$ が $t$ 個あると仮定します。$r$ は偶数なので $p-r$ は奇数です。$r\gt p/2$ なので、
\[p-r\lt\frac{p}{2}\]
となります。つまり $t$ は $p/2$ より小さな奇数の個数と一致するので
\[t\equiv 1+3+5+\cdots +\frac{p-1}{2}\quad (\mathrm{mod}\:2)\]
これに偶数をいくつ加えても合同なので、等差級数の公式を用いて
\[\begin{align*}t\equiv& 1+2+3+4+5+\cdots +\frac{p-1}{2}\\[6pt]
\equiv& \frac{1}{2}\,\frac{p-1}{2}\left(1+\frac{p-1}{2}\right)=\frac{p^2-1}{8}\quad (\mathrm{mod}\:2)\end{align*}\]
が得られます(証明終)。

相互法則(Reciprocity Law)

 次は相互法則(reciprocity law) の証明を行ないます。

【定理F15:平方剰余の相互法則】
$p, q$ を相異なる $2$ つの奇素数とするとき、
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]

相互法則はオイラーによって予想され、ガウスによって証明されました。
この定理は $\mathrm{mod}\:p$ と $\mathrm{mod}\:q$ の世界を結びつけるもので、初等整数論の到達点であり、近代数論の土台となる重要定理といわれています。

証明には ガウスの補題 を用います:

$p$ が奇素数、$(a,\:p)=1$ であるとき、
\[1a,\:2a,\:3a,\:\cdots,\:\frac{p-1}{2}a\]を $p$ で割って余りを並べて、$p/2$ より大きな数が $t$ 個あるならば、
\[\left(\frac{a}{p}\right)=(-1)^t\]

ガウスの補題において $a=q$ とおくと、
\[qx\quad \left(x=1,\:2,\:\cdots,\:\frac{p-1}{2}\right)\]
を $p$ で割ったときの余りを並べたときに、$p/2$ より大きいものが $n$ 個あるならば
\[\left(\frac{q}{p}\right)=(-1)^n\]
が成り立ちます。同様に、
\[py\quad \left(y=1,\:2,\:\cdots,\:\frac{q-1}{2}\right)\]
を $q$ で割ったときの余りを並べたときに、$q/2$ より大きいものが $m$ 個あるとすれば
\[\left(\frac{p}{q}\right)=(-1)^m\]
が成り立ちます。すなわち
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^n (-1)^m=(-1)^{m+n}\]
なので、
\[m+n\equiv \left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)\quad (\mathrm{mod}\:2)\tag{R1}\]
が成り立つ(両辺の偶奇が一致する)ことを示せれば、相互法則
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\tag{R2}\]
を証明できたことになります。

[R1の証明] 格子点を使って証明します。

平方剰余の相互法則(格子点による証明)

$\displaystyle\left(\frac{p+1}{2},\:\frac{q+1}{2}\right)$ を点 $\mathrm{C}$ として、$\mathrm{ABCD}$ の内側に格子点を打ち、原点 $\mathrm{O}$ と $\mathrm{L}(p/2,\:q/2)$ を結ぶ直線を引きます。直線 $\mathrm{OL}$ の方程式は
\[y=\frac{qx}{p}\]
です。また、直線 $\mathrm{OL}$ を $y$ 軸方向と $x$ 軸方向に $1/2$ だけ平行移動させた直線をそれぞれ $\mathrm{GG’},\:\mathrm{HH’}$ とします。$qx$ を $p$ で割ったときの余りを $r$ とすると
\[qx=py+r\]
と表せます。この式を変形すると
\[\frac{qx}{p}=p+\frac{r}{p}\]
となります。$r$ が $p/2$ より大きいということは、
\[\frac{r}{p}\gt \frac{1}{2}\]
すなわち $qx/p$ の小数部分が $1/2$ よりも大きいことを意味します。

これを図で考えると、$\mathrm{P}$ は直線 $\mathrm{MP}$ 上で、$\mathrm{P}$ を挟む $2$ つの格子点の間の半分より上にあることになります。言い換えると、$\mathrm{P}$ から縦に最も近い格子点は $\mathrm{OL}$ より上側のほうだということです。つまり $n$ は平行四辺形 $\mathrm{OGG’L}$ の内側にある格子点ということになります。

同様に $m$ は平行四辺形 $\mathrm{OHH’L}$ の内側にある格子点です。角にある小さな三角形も加えても格子点の数は変わらないので、$m+n$ は六角形 $OGG’CH’H$ の内部にある格子点の数に等しいことになります。

ここで $\mathrm{OC}$ の中点 $\displaystyle\left(\frac{p+1}{4},\:\frac{q+1}{4}\right)$ は六角形の対称の中心で、格子点はこの点に関して $2$ つずつ対称に存在していることになります。つまり、$m+n$ が偶数か奇数であるかは、$\displaystyle\left(\frac{p+1}{4},\:\frac{q+1}{4}\right)$ 自身が含まれるかどうかで決まります(含まれるなら奇数、含まれないなら偶数です)。含まれるときは、$s,\:t$ を整数として
\[\frac{p+1}{4}=s,\quad\frac{q+1}{4}=t\]
これを少し変形して
\[\frac{p-1}{2}=2s-1,\quad\frac{q-1}{2}=2t-1\]
となります。すなわち $m+n$ が奇数であるということは $\displaystyle\left(\frac{p-1}{2},\:\frac{q-1}{2}\right)$ がともに奇数であることと同じです。したがって
\[m+n\equiv \left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)\quad (\mathrm{mod}\:2)\tag{R1}\]
が成り立つことがわかり、これによって平方剰余の相互法則

\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\tag{R2}\]
が示されました。

mod 4 による判定

奇数を $4$ で割ったときの余りは $1$ か $3$ のどちらかです。すなわち

$x\equiv 1\quad (\mathrm{mod}\:4)$ または $x\equiv 3\quad (\mathrm{mod}\:4)$

となります。$x\equiv 1\quad (\mathrm{mod}\:4)$ のときは
\[\frac{x-1}{2}=\frac{4k+1-1}{2}=2k\]
であり、$x\equiv 3\quad (\mathrm{mod}\:4)$ のときは
\[\frac{x-1}{2}=\frac{4k+3-1}{2}=2k+1\]
となります。したがって、$p\equiv 1$ または $q\equiv 1\:(\mathrm{mod}\:4)$ のときは $\displaystyle\frac{p-1}{2}\frac{q-1}{2}$ は偶数、$p\equiv 3$ かつ $q\equiv 3\:(\mathrm{mod}\:4)$ のときは $\displaystyle\frac{p-1}{2}\frac{q-1}{2}$ は奇数となります。これを使って相互法則を書き直しておきます。

【定理F16:平方剰余の相互法則】
$p, q$ を相異なる $2$ つの奇素数とするとき、
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=\begin{cases}
1 & (p\equiv 1\: \lor \: q\equiv 1\quad (\mathrm{mod}\:4))\\[6pt]
-1 & (p\equiv 3\: \land\: q\equiv 3\quad (\mathrm{mod}\:4))\end{cases}\]

平方剰余の例題

これまでに得た知識を総合すると、どのような方程式についても、平方剰余/非剰余の判定ができます(もちろん $a$ や $p$ があまりに大きな値であれば計算は大変です)。判定に必要となる定理をすべて再掲します。

 $p,\:q$ は奇素数、$(a,\:p)=(b,\:p)=1$

[定理F11:積の法則]
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]

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

[定理F14:第2補充法則]
\[\left(\frac{2}{p}\right)= (-1)^{\frac{p^2-1}{8}}\]

[定理F15:相互法則]
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]

それでは合同方程式
\[x^2\equiv 18\quad (\mathrm{mod}\:31)\]
に解があるかどうかを調べましょう(このような簡素な問いに答えるために、私たちはここまで頑張ってきたのです!)。ルジャンドル記号を用いて表すと
\[\left(\frac{18}{31}\right)\]
の値が $1$ なら解があり(平方剰余であり)、$-1$ なら解なし(平方非剰余)です。まずは積の形に分解します。
\[\left(\frac{18}{31}\right)=\left(\frac{2\cdot 3^2}{31}\right)=\left(\frac{2}{31}\right)\left(\frac{3}{31}\right)^2\]
$\displaystyle\left(\frac{2}{31}\right)$ は第2補充法則によって計算できます。
\[\left(\frac{2}{31}\right)=(-1)^{\frac{31^2-1}{8}}=1\]
$\displaystyle\left(\frac{3}{31}\right)$ の計算には相互法則を用います。相互法則によれば
\[\left(\frac{3}{31}\right)\left(\frac{31}{3}\right)=(-1)^{\frac{3-1}{2}}(-1)^{\frac{31-1}{2}}=1\]
なので、
\[\left(\frac{3}{31}\right)=\left(\frac{31}{3}\right)\]
と書き直せます。このように変形できることが相互法則の恩恵なのです。なぜなら、$31$ は $\mathrm{mod}\:3$ において $1$ と合同なので、
\[\left(\frac{31}{3}\right)=\left(\frac{1}{3}\right)=1\]
と計算できます (任意の $p$ で、$x^2\equiv 1$ は解をもちます)。したがって、
\[\left(\frac{18}{31}\right)=1\]
となり、$x^2\equiv18\:(\mathrm{mod}\:31)$ は解をもつことがわかりました。すなわち $18$ は $31$ の平方剰余です。

Excelで平方剰余の問題を解いてみます

コンピュータの力を借りると、平方剰余/非剰余の判定のみならず、実際の解を求めることも比較的容易にできます。さきほどの合同方程式
\[x^2\equiv18\quad (\mathrm{mod}\:31)\]
を満たす最小の整数 $x$ を求めてみます。

Excelによる平方剰余の解法

A 列に $1$ から $10$ までの整数、B 列にその平方数、C 列には平方数を $31$ で割った値が並んでいます。余りが $18$ となっているセル(緑色に塗られているところ)があります。すなわち解が $x=7$ であることがわかります。このように問題をビジュアル化できるので、Excel は数論にとって相性の良いツールです。

VBAで平方剰余の問題を解いてみます

VBA で平方剰余の問題を解く QR関数をつくっておきました。QR は Quadratic Residue(平方剰余)の頭文字です。VBE を起動して標準モジュールに貼りつけると、ワークシートで Excel 関数のように扱えます。

'VBA Quadratic Residue

Function QR(a As Long, p As Long) As Variant
  Dim x As Long

  'pについてaと合同な最小数を得る
  Do While a > p
    a = a - p
  Loop

  '解が見つからない場合はFalseを返す
  QR = False

  'x^2をpで割った余りがaであればxは解
  For x = 1 To p - 1
    If x ^ 2 Mod p = a Then
      QR = x
      Exit For
    End If
  Next x

End Function

QR関数を使うときはセルに「=QR(a,p)」の形で入力します。もし解がなければ(平方非剰余であるならば)、この関数は False を返します。さきほどの合同方程式
\[x^2\equiv18\quad (\mathrm{mod}\:31)\]をこの関数で解いてみましょう。
「=QR(18,31)」と入力すると、7 という値が返ってきます。つまり、$18$ は $31$ の平方剰余であり、方程式の解は $x=7$ です。

エクセルや数学に関するコメントをお寄せください