証明路開発支援システム(16) - 非専門的シンギュラリティー研究所

『ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)』と『数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論』の「ガウスの和」の証明については今後見ていくことにします。『ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)』の他の証明についても今後見ていきます。

まずは「平方剰余の相互法則(5)」をツリーのように書き直していくことにします。数式が多いので「証明路」にするのは難しそうですが他のものにも使えそうなのでやっておきます。

『発見・予想を積み重ねる ―それが整数論』、『はじめての数論　原著第4版』の方法の方が簡単そうなのですが、まず「平方剰余の相互法則(5)」の方から見ていきます。

『ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)』の表(p.169)も参考にします。

第1証明	数学的帰納法
第2証明	2次形式
第3証明	ガウスの補題
第4証明	ガウス和
第5証明	ガウスの補題
第6証明	ガウス和
第7証明	ガウス和(ガウス周期)

「平方剰余の相互法則(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$ となります。
- $kx = i$ は整数かつ $k ≦ 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]$ 、 … 、 $\left[ \left[\cfrac{k}{x}\right] x \right]$ は $k$ より小さい数となります。
$i \ge \left[\cfrac{k}{x}\right] + 1$ とすると $i \ge \left[\cfrac{k}{x}\right] + 1 > \cfrac{k}{x}$ より $ix > k$ となります。
よって $\left[ \left( \left[\cfrac{k}{x}\right] + 1\right) x \right]$ 、 $\left[ \left( \left[\cfrac{k}{x}\right] + 2\right) x \right]$ 、 $\left[ \left( \left[\cfrac{k}{x}\right] + 3\right) x \right]$ 、 … は $k$ より大きい数となります。
よって、、、 … 、の
- 最初の $\left[\cfrac{1}{x}\right]$ 個は $0$
- 次の $\left[\cfrac{2}{x}\right] - \left[\cfrac{1}{x}\right]$ 個は $1$
- 次の $\left[\cfrac{3}{x}\right] - \left[\cfrac{2}{x}\right]$ 個は $2$
- ……
となります。
よって
$\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{q}{2}$ となるので
$\left[\cfrac{p - 1}{2}\cdot\cfrac{q}{p}\right] = \cfrac{q - 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 = \left\{1, 2, 3, … , \cfrac{p-1}{2}\right\}$ 、
- $-S = \left\{p-1, p-2, p-3, … , p-\cfrac{p-1}{2}\right\}$
とおきます。
$x$ を $p$ で割った余りを $r(x)$ とします( $0 \le r \le p-1$ )。
$a$ を $p$ で割り切れない整数とします。
を
- $r(x) ∈ S$ のとき $f(x)$ = $0$ 、
- $r(x) \not ∈ S$ のとき $f(x) = 1$
とします。
を
- $r(x) ∈ S$ のとき $g(x) = r(x)$ 、
- $r(x) \not ∈ S$ のとき $g(x) = p - r(x)$
とします。
すると
- $g(x) = (-1)^{f(x)}・r(x) + pf(x)$
- $g(x) \equiv (-1)^{f(x)}・x \pmod p$
となります。
をとおくとは全単射となります。
- なぜならとすると
  - $g(ax) = g(ay)$
  - $(-1)^{f(ax)}・ax \equiv (-1)^{f(ay)}・ay \pmod p$
  - $(-1)^{f(ax)-f(ay)}・ax \equiv ay \pmod p$
  - $(-1)^{f(ax)-f(ay)}・x \equiv y \pmod p$
  なのでかつとなります。
- $h$ は単射となります。 $S$ は有限集合なので $h$ は全単射となります。
よって $\displaystyle \prod_{x \in S} g(ax) = \prod_{x \in S} x$ となります。
よって
$\displaystyle \prod_{x \in S} ax = \prod_{x \in S} \left( (-1)^{f(ax)}・g(ax) \right) = \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} g(ax) = \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} x$
となります。
よって
$\displaystyle \prod_{x \in S} \left( (-1)^{f(ax)} \right) = \left(\prod_{x \in S} ax \right)/\left(\prod_{x \in S} x \right) = a^{\frac{p-1}{2}}$
となります。
$S$ の元 $s$ で、 $as$ を $p$ で割った余りが $-S$ に含まれるものの個数を $n$ とすると
$\begin{eqnarray*} a^{\frac{p-1}{2}} & = & (a \cdot 1)(a \cdot 2) \cdots \left( a \cdot \frac{p-1}{2} \right) / \left( 1 \cdot 2 \cdots \frac{p-1}{2} \right) \\ & = & \left(\frac{a}{g(a)} \right) \left(\frac{2a}{g(2a)} \right) \cdots \left( \frac{ \frac{p-1}{2}a } { g \left( \frac{p-1}{2}a \right)} \right) ≡ (-1)^n \ (\mathrm{mod} \ p) \end{eqnarray*}$
となります。
の元で、
- $as$ を $p$ で割った余り $r(as)$ が $S$ に含まれるときの $r(as)$ の和を $x$ 、
- $as$ を $p$ で割った余り $r(as)$ が $-S$ に含まれるときの $r(as)$ の和を $y$
とおくと、

となります。
ここで $h$ は全単射であることから
$\displaystyle g(a) + g(2a) + \cdots + g \left( \frac{p-1}{2}a \right) = 1 + 2 + \cdots + \frac{p-1}{2} = \frac{(p-1)(p+1)}{8}$
となっているので
$\displaystyle 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} \right)q - pL \\ & = & \frac{(p-1)(p+1)}{8}q - pL \end{eqnarray*}$
となって $\displaystyle x + np - y = \frac{(p-1)(p+1)}{8}$ とあわせると
$\displaystyle np = pL + 2y - \frac{(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)$ は偶数になります。
よって
$\displaystyle \left(\frac{q}{p}\right) = (-1)^{n} = (-1)^{L}$
となります。

[証明終わり]

【平方剰余の相互法則】

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

[証明]

$\displaystyle L = \left[\frac{q}{p}\right] + \left[2 \cdot \frac{q}{p}\right] + \cdots + \left[\frac{p-1}{2} \cdot \frac{q}{p}\right]$ 、
$\displaystyle M = \left[\frac{p}{q}\right] + \left[2 \cdot \frac{p}{q}\right] + \cdots + \left[\frac{q-1}{2} \cdot \frac{p}{q}\right]$

命題3より
- $\displaystyle \left(\frac{p}{q}\right) = (-1)^{M}$ 、
- $\displaystyle \left(\frac{q}{p}\right) = (-1)^{L}$
となります。
命題2より
$\displaystyle L + M = \frac{(p-1)(q-1)}{4}$
となるので
$\displaystyle \left(\frac{q}{p}\right) \left(\frac{p}{q}\right) = (-1)^{L + M} = (-1)^{ \frac{(p-1)(q-1)}{4} }$
となります。