非専門的シンギュラリティー研究所

無限に動き続けるシステムを表す方法を AI なども使って考えていきます。

証明路開発支援システム(14)

証明路開発支援システム

平方剰余の相互法則についても、

証明路
プログラム形式の証明
証明を生成するプログラム

のどれかに対応できるようにツリー形式に書き直すことにします。まず「平方剰余の相互法則(2) - 非専門的シンギュラリティー研究所」を見ていきます。『平方剰余の相互法則: ガウスの全証明』、『数論への出発増補版』を参考にしています。

(1) $p$ が素数のときに $\mathbb{Z}/p\mathbb{Z}$ は体になります。

[証明]

$p$ は素数なので、整数 $x$ に対して、 $mx + np = 1$ を満たす整数 $m$ , $n$ が存在します。
$mx≡1 \ (\mathrm{mod} \ p)$ となるので $m + \mathbb{Z}$ は $x + \mathbb{Z}$ の乗法の逆元となります。

[証明終わり]

$\mathbb{Z}/p\mathbb{Z}$ を $F_p$ と書きます。

(2) $x$ , $y$ を可換群 $G$ の元とします。 $x$ の位数が $m$ 、 $y$ の位数が $n$ 、 $m$ と $n$ が互いに素であるとき、 $xy$ の位数は $mn$ となります。

[証明]

となることを証明します。
- $(xy)^{mn} = (x^{mn})(y^{mn}) = (x^{m})^n(y^{n})^m = 1$ となります。
ならばはの倍数となることを証明します。
- $(xy)^k = 1$ とします。
- $1 = (xy)^{km} = (x^{km})(y^{km}) = y^{km}$ より $km$ は $n$ の倍数となります。
- $m$ と $n$ が互いに素なので $k$ は $n$ の倍数となります。
- $1 = (xy)^{kn} = (x^{kn})(y^{kn}) = x^{kn}$ より $kn$ は $m$ の倍数となります。
- $m$ と $n$ が互いに素なので $k$ は $m$ の倍数となります。
- よって $k$ は $mn$ の倍数となります。

[証明終わり]

(3) $F$ を体、 $f(X)$ を $F$ の元を係数とする $n$ 次( $n \ge 0$ )の多項式( $f(X) \ne 0$ )とすると、 $f(a) = 0$ を満たす $F$ の元 $a$ の個数は $n$ 以下となります。

[証明]

に関する帰納法によって証明します。
1. の場合を証明します。
  - $f(a) = 0$ を満たす $F$ の元は $0$ 個なので成り立ちます。
2. でより小さい場合は成り立っているとして、の場合を証明します。
  - $f(a) = 0$ とすると、 $f(X)$ を $(X - a)$ で割ると余りは $0$ となります。
  - よって $f(X) = (X - a)g(X)$ を満たす $n-1$ 次以下の多項式 $g(X)$ が存在します。
  - 帰納法の仮定により $g(b) = 0$ を満たす $b$ は $n-1$ 個以下なので $f(a) = 0$ を満たす $a$ は $n$ 個以下となります。

[証明終わり]

(4) $F$ が有限体のとき $F^* = F - \{0\}$ は乗法に関して巡回群になります。

[証明]

$x$ を $F^*$ の位数が最大の元とします。
であることを証明します。
- $x$ の位数を $m$ とします。
- $y$ を $G$ の元とします。
- であることを証明します。
  - $y$ の位数を $n$ とし、 $k$ を $m$ と $n$ の最大公約数とします。
  - $z = y^{(n/k)}$ とおくと $z^m = y^{(mn/k)} = (y^n)^{(m/k)} = 1$ となります。
  - $\langle x \rangle = \{x^e | e = 0, 1, 2, … , m-1\}$ の元 $x^e$ は $(x^e)^m = (x^m)^e = 1$ を満たします。
  - (3)から $a^m = 1$ を満たす $F^*$ の元は最大 $m$ 個なので、 $a^m = 1$ を満たす $a$ はすべて $\langle x \rangle$ の元となります。
  - よってはの元となります。
    1. $n/k = 1$ ならば $y = z ∈ \langle x \rangle$ となります。
    2. のとき
      - $w = x^k・y$ とおくと、(2)から $w の位数 = x^k の位数 × y の位数 = (m/k)・n = mn/k > m$ となります。
      - これは $x$ の位数が最大であることに反します。

[証明終わり]

(5) $F_p^*$ は巡回群になります。(原始根定理)

[証明]

(1)と(4)から成り立ちます。

[証明終わり]

「原始根定理」についても後で見ていきます。

を参照します。

(6) (フェルマーの小定理) $p$ が $2$ ではない素数、 $a$ が $p$ と素な整数のとき、 $a$ の $p-1$ 乗は $p$ を法として $1$ と合同になります。

[証明]

(5)から $F_p^*$ の生成元が存在します。
$x$ を $F_p^*$ の生成元とすると、 $x^{p-1} = 1$ となります。
$a$ を含む剰余類はある $x^e$ に等しいので $a^{p-1} + p\mathbb{Z} = (x^e)^{p-1} = (x^{p-1})^e = 1$ となります。

[証明終わり]

(7) (オイラーの規準) $p$ が $2$ ではない素数、 $a$ が $p$ と素な整数のとき

$a$ が法 $p$ に関する平方剰余のとき、 $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りは $1$ 、

$a$ が法 $p$ に関する平方剰余ではないとき、 $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りは $p-1$ になります。

[証明]

(6)から $a^{p-1}≡1 \ (\mathrm{mod} \ p)$ となるので $a^{ (p-1)/2}≡±1 \ (\mathrm{mod} \ p)$ となります。
平方剰余の定義より「 $a$ が法 $p$ に関する平方剰余 ⇔ $x$ が存在して $a≡x^2 \ (\mathrm{mod} \ p)$ 」です。
「が存在して ⇔ 」を証明します。
1. $a≡x^2 \ (\mathrm{mod} \ p)$ とすると $a^{ (p-1)/2}≡x^{p-1}≡1 \ (\mathrm{mod} \ p)$ となります。
2. 逆にとします。
  - (5)から $F_p^*$ の生成元が存在します。
  - $r$ を $F_p^*$ の生成元として、 $a + p\mathbb{Z} = r^e$ とします。
  - $(r^e)^{ (p-1)/2} = 1$ より $e(p-1)/2$ は $p-1$ の倍数となります。
  - $e(p-1)/2 = c(p-1)$ とおくと $e = 2c$ となります。
  - $a + p\mathbb{Z} = r^e = (r^c)^2$ となり、 $r^c$ の代表元を $x$ とおくと $a≡x^2 \ (\mathrm{mod} \ p)$ となります。

[証明終わり]

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

作者:ウィルソン R. J.
近代科学社

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

作者:後藤四郎
共立出版

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

作者:雪江明彦
日本評論社

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

作者:銀林浩
筑摩書房

発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

作者:安福悠
オーム社

はじめての数論　原著第4版

はじめての数論　原著第4版

丸善出版

数論序説

作者:小野孝
裳華房

群論日評ベーシック・シリーズ

群論日評ベーシック・シリーズ

作者:榎本直也
日本評論社

代数学１　群論入門　第２版

代数学１　群論入門　第２版

作者:雪江明彦
日本評論社

代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

作者:桂利行
東京大学出版会

代数系入門 (松坂和夫数学入門シリーズ 3)

代数系入門 (松坂和夫数学入門シリーズ 3)

作者:松坂和夫
岩波書店

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

日本評論社

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

作者:西来路文朗,清水健一
講談社

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

作者:倉田令二朗
日本評論社

数論への出発増補版

数論への出発増補版

作者:藤崎源二郎
日本評論社

共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

作者:斎藤秀司
共立出版