第５章 順序代数構造 - プログラミング原論／Elements of Programming Wiki

概要

基本的な代数構造である群・環の構造を導入しました。最大公約数(G.C.D)を求めるアルゴリズム（ユークリッドの互除法）が有効となる
代数的性質をコンセプトとして記述しています。さらに、ユークリッド互除法より高速なSteinのGCDアルゴリズムを導入しています。
この章では、特定のアルゴリズムに対してそれを成立させるためにどのようなコンセプトが必要になるか、を考えるのに慣れることを
目標にしています。

命題の証明の概要

補題5.1 単位元がの２つあると仮定してを示す。

補題5.2 任意の正整数はとかけるので0,1,2,3,4でを示す。（ref.フェルマーの小定理）

補題5.3

補題5.4 定理5.1と同様。

補題5.5 と と加算が可換であることより。

補題5.6 帰納法により。

補題5.7 両辺にを加える。

補題5.8 補題5.7と同様。

補題5.15 に を代入する。

補題5.16　対偶である「奇数の平方は奇数である。」ことを示す。

補題5.17 与えられたモノイドが整数環、または自然数（0を含む）に同型となることを示す。

本文の修正

p.82 6行目以降、この章全体
定義域 → 整域

p.83 5行目
ユークリッド環ではquotientは半環の要素を返します。通分出来る分数に対し、ユークリッド互除法をオリジナルの枠組みで使用することはできません。例えば、gcd(1/2, 3/4) = 1/4などです。分数に対してgcdアルゴリズムを実現するために元々のユークリッド互除法を、ユークリッド半加群のコンセプトへ拡張します。ユークリッド半加群ではquotientが異なる型を返すことが可能となり、gcdは終了します。

p.90 1行目
すべての公理を満たしているモデルで、その命題を満たさないものが存在する場合、その命題は公理の集合から独立である、と言う。

p.90 12行目
任意の結合則と可換則を満たす演算に対して、同時にバラバラな順序で簡約可能である。