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

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

数学ゲーム(34)

数学ゲーム

フェルマーの小定理パズル(11)

「数学ゲーム(24) - 非専門的シンギュラリティー研究所」、「数学ゲーム(25) - 非専門的シンギュラリティー研究所」で考察した証明の残りの部分を見ていきます。

「素数約数判定システム」、「帰納法システム」があるとします。

フェルマーの小定理の二項定理を使った帰納法による証明

素数に関して以下のことが成り立ちます。

(1) 素数 $p$ で割り切れる $1$ 以上の整数 $a$ は $a \ge p$
(2) $a, b$ が $1$ 以上の整数で $ab$ が素数 $p$ で割り切れるならば $a$ が $p$ で割り切れるか、または $b$ が $p$ で割り切れる

二項定理より $p$ が素数、 $k = 1, 2, \cdots, p-1$ のとき
$\displaystyle c = \frac{p!}{k! \ (p-k)!}$
は整数となります。 $p \cdot (p-1)! = k! \cdot (p-k)! \cdot c$ となりますが、 $k! \cdot (p-k)!$ は $p$ より小さい整数の積なので(1)、(2)より $k! \cdot (p-k)!$ は $p$ で割り切れません。よって(2)より $c$ は $p$ で割り切れます。

「素数約数判定システム」はこのようにある整数がある素数で割り切れるかどうかを判定することができるとします。

よって二項定理より任意の整数 $n$ に対して
$(n + 1)^{p} \equiv n^p + 1 \pmod p$
が成り立ちます。

$0^{p} \equiv 0 \pmod p$ が成り立ちます。
$n^{p} \equiv n \pmod p$ が成り立つならば、 $(n (+ 1))^{p} \equiv n^p (+ 1) \equiv n (+ 1) \pmod p$ が成り立ちます。

「帰納法システム」により

$(0 (+ \forall n))^{p} \equiv 0 (+ \forall n) \pmod p$ が成り立ちます。

よって任意の自然数 $n$ に対して $n^{p} \equiv n \pmod p$ が成り立ちます。

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

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

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

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

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

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

【電子復刻版】bit 1988年04月号(通巻230号)

【電子復刻版】bit 1988年04月号(通巻230号)

共立出版

【電子復刻版】bit 1989年04月号(通巻242号)

【電子復刻版】bit 1989年04月号(通巻242号)

共立出版

新しいプログラミング・パラダイム

新しいプログラミング・パラダイム

共立出版

岩波講座ソフトウェア科学〈〔理論〕12〉計算モデルの基礎理論

岩波講座ソフトウェア科学〈〔理論〕12〉計算モデルの基礎理論

作者:井田哲雄
岩波書店