平方剰余の相互法則(5) - エレファント・コンピューティング調査報告

今回は「平方剰余の相互法則ガウスの全証明」IIIに従って証明します。

【ガウス記号】

整数でない実数 $x$ に対して、 $x$ を超えない最大整数を $[x]$ で表します。これをガウス記号といいます。 $[x] < x < [x] + 1$ となります。( $x$ が整数のときにも $[x] = x$ として定義されている場合があります。この関数は floor と呼ばれることがあります。)

【命題1】

$x$ 、 $2x$ 、 $3x$ 、… 、 $nx$ を整数でない実数とし、 $h = [nx]$ とおきます。このとき
$[x] + [2x] + [3x] + \cdots + [nx] + \left[\frac{1}{x}\right] + \left[\frac{2}{x}\right] + \left[\frac{3}{x}\right] + \cdots + \left[\frac{h}{x}\right] = nh$
となります。

[証明]
$\cfrac{1}{x}$ 、 $\cfrac{2}{x}$ 、 $\cfrac{3}{x}$ 、… 、 $\cfrac{h}{x}$ の中のある $\cfrac{i}{x}$ がある整数 $k$ に等しいとすると、 $kx = i ≦ h$ なので $k ≦ \cfrac{h}{x} = \cfrac{[nx]}{x} ≦ \cfrac{nx}{x} = n$ となりますが、「 $x$ 、 $2x$ 、 $3x$ 、… 、 $nx$ は整数ではない」としていますので、このようにはなりません。よって $\cfrac{1}{x}$ 、 $\cfrac{2}{x}$ 、 $\cfrac{3}{x}$ 、… 、 $\cfrac{h}{x}$ はすべて整数ではありません。
$[x]$ 、 $[2x]$ 、 $[3x]$ 、 … 、 $[nx]$ について考えます。 $i ≦ \left[\cfrac{k}{x}\right]$ とすると $i ≦ \left[\cfrac{k}{x}\right] < \cfrac{k}{x}$ より $ix < k$ となります。よって $[x]$ 、 $[2x]$ 、 $[3x]$ 、 … 、 $[nx]$ の $\left[\cfrac{1}{x}\right]$ 番目までの数 $m_1$ は $m_1 < 1$ となります。同様に $\left[\cfrac{2}{x}\right]$ 番目までの数 $m_2$ は $m_2 < 2$ 、 $\left[\cfrac{3}{x}\right]$ 番目までの数 $m_3$ は $m_3 < 3$ 、… となります。よって
$\begin{eqnarray*} & & [x] + [2x] + [3x] + \cdots + [nx] \\ & = & 0・\left[\cfrac{1}{x}\right] + 1・\left(\left[\cfrac{2}{x}\right] - \left[\cfrac{1}{x}\right]\right) + 2・\left(\left[\cfrac{3}{x}\right] - \left[\cfrac{2}{x}\right]\right) \\ & & + \cdots + (h - 1)\left(\left[\cfrac{h}{x}\right] - \left[\cfrac{h-1}{x}\right]\right) + h\left(n - \left[\cfrac{h}{x}\right]\right) \\ & = & hn - \left(\left[\cfrac{1}{x}\right] + \left[\cfrac{2}{x}\right] + \left[\cfrac{3}{x}\right] + \cdots + \left[\cfrac{h}{x}\right]\right) \end{eqnarray*}$
となります。
[証明終わり]

【命題2】

$p$ 、 $q$ が $2$ ではない異なる素数のとき、
$L = \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right]$ 、
$M = \left[\cfrac{p}{q}\right] + \left[2 \cdot \cfrac{p}{q}\right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q}\right]$
とおくと、
$L + M = \cfrac{(p-1)(q-1)}{4}$
が成り立ちます。

[証明]
$q < p$ とすると $pq - p < pq - q$ より $p(q - 1) < q(p - 1)$ となります。よって $\cfrac{q - 1}{2} < \cfrac{p - 1}{2}\cdot\cfrac{q}{p} < \cfrac{k}{2}$ 、 $\left[\cfrac{p - 1}{2}\cdot\cfrac{q}{p}\right] = \cfrac{k - 1}{2}$ となります。命題1で $x = \cfrac{q}{p}$ 、 $n = \cfrac{p - 1}{2}$ とおくと
$\begin{eqnarray*} & & \left[\frac{q}{p}\right] + \left[2\cdot\frac{q}{p}\right] + \cdots + \left[\frac{p-1}{2}\cdot\frac{q}{p}\right] \\ & & + \left[\frac{p}{q}\right] + \left[2\cdot\frac{p}{q}\right] + \cdots + \left[\frac{q-1}{2}\cdot\frac{p}{q}\right] \\ & = & \cfrac{(p-1)(q-1)}{4} \end{eqnarray*}$
が成り立ちます。
$p < q$ としても同様に
$L + M = \cfrac{(p-1)(q-1)}{4}$
が成り立ちます。
[証明終わり]

【命題3】

$p$ 、 $q$ が $2$ ではない異なる素数のとき、
$L = \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right]$
とおくと、
$\left(\cfrac{q}{p}\right) = (-1)^{L}$
が成り立ちます。

[証明]
$S = \{1, 2, 3, … , \cfrac{p-1}{2}\}$ 、 $-S = \{p-1, p-2, p-3, … , p-\cfrac{p-1}{2}\}$ とおきます。
$S$ の元 $s$ で、 $as$ を $p$ で割った余りが $-S$ に含まれるものの個数を $n$ とします。
$as$ を $p$ で割った余りが $r$ のとき、 $r$ が $S$ に含まれるとき $g(as) = r$ 、 $-S$ に含まれるとき $g(as) = p - r$ とおきます。
「ガウスの補題」の証明と同様に
$\begin{eqnarray*} a^{\frac{p-1}{2}} & = & (a \cdot 1)(a \cdot 2) \cdots (a \cdot \frac{p-1}{2}) / (1 \cdot 2 \cdots \frac{p-1}{2}) \\ & = & \left(\frac{a}{g(a)} \right) \left(\frac{2a}{g(2a)} \right) \cdots \left( \frac{ \frac{p-1}{2}a } { g( \frac{p-1}{2}a)} \right) ≡ (-1)^n \ (\mathrm{mod} \ p) \end{eqnarray*}$
となります。
$S$ の元 $s$ で、 $as$ を $p$ で割った余り $r$ が $S$ に含まれるときの $r$ の和を $x$ 、 $as$ を $p$ で割った余り $r$ が $-S$ に含まれるときの $r$ の和を $y$ とおくと、
$g(a) + g(2a) + … + g( \frac{p-1}{2} ) = x + (np - y)$
となります。
ここで
$g(a) + g(2a) + … + g( \frac{p-1}{2} ) = 1 + 2 + … + \frac{p-1}{2} = \frac{(p-1)(p+1)}{8}$
となっているので
$x + np - y = \frac{(p-1)(p+1)}{8}$
となります。
一方 $kq$ を $p$ で割った余りは $kq - p[\frac{kq}{p}]$ なので
$\begin{eqnarray*} x + y &= & \left(q - p\left[\frac{q}{p}\right]\right) + \left(2q - p\left[\frac{2q}{p}\right]\right) + \cdots + \left( \frac{p-1}{2}q - p\left[\frac{\frac{p-1}{2}q}{p}\right]\right) \\ & = & \left(1 + 2 + \cdots + \frac{p-1}{2}q\right) - pL \\ & = & \frac{(p-1)(p+1)}{8}q - pL \end{eqnarray*}$
となって $x + np - y = \frac{(p-1)(p+1)}{8}$ とあわせると
$np = pL + 2y - \cfrac{(p-1)(p+1)}{8}(q-1)$
が成り立ちます。 $p$ は奇数なので、 $p-1$ 、 $p+1$ は偶数、 $\cfrac{p-1}{2}$ 、 $\cfrac{p+1}{2}$ のどちらかは偶数なので、 $(p-1)(p+1)$ は $8$ の倍数であり、 $q$ は奇数なので $q-1$ は偶数であるから $\cfrac{(p-1)(p+1)}{8}(q-1)$ は偶数になります。よって
$\left(\cfrac{q}{p}\right) = (-1)^{n} = (-1)^{L}$
となります。
[証明終わり]

【平方剰余の相互法則】

$p$ 、 $q$ が $2$ ではない異なる素数のとき、
$\left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = (-1)^{ \frac{(p-1)(q-1)}{4} }$
が成り立ちます。

[証明]
$L = \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right]$ 、
$M = \left[\cfrac{p}{q}\right] + \left[2 \cdot \cfrac{p}{q}\right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q}\right]$
とおくと、
命題3より
$\left(\cfrac{p}{q}\right) = (-1)^{M}$ 、
$\left(\cfrac{q}{p}\right) = (-1)^{L}$
となります。
命題2より
$L + M = \cfrac{(p-1)(q-1)}{4}$
となるので
$\left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = (-1)^{L + M} = (-1)^{ \frac{(p-1)(q-1)}{4} }$
となります。
[証明終わり]