next up previous contents index
: 単項イデアルと 1 変数連立代数方程式系の解法 : 1 変数多項式の GCD とその応用 : 1 変数多項式の GCD とその応用   目次   索引

ユークリッドのアルゴリズム

数学科の学生は 代数学の講義で, ``ユークリッド整域'' なる概念を習ったこと と思う. 整数環 ${\bf Z}$, 一変数多項式環 ${\bf k}[x]$ はともに ユークリッド整域であり, 次の割算定理が成り立つ: $R$ を 整数環または一変数多項式環とする. このとき $R$$0$ でない任意の元 $f$, $g$ に対して,

\begin{displaymath}f = q g + r , \quad {\rm deg}(r) < {\rm deg}(g) \end{displaymath}

を満たす $R$ の元 $q$, $r$ が存在する. ここで $R={\bf Z}$ のとき ${\rm deg}(f) = \vert f\vert$, $R={\bf k}[x]$ のときは ${\rm deg}(f) = f \mbox{の次数}\, $ と定義する

ユークリッド整域はこの割算定理の成立を仮定した 整域であり, ユークリッド整域で議論を展開しておくことにより, 整数での議論もー変数多項式での議論も共通化が 可能である. 計算機科学における, Object 指向, 部品化, 抽象データ型等の概念も, このような現代数学の考え方-- 抽象化, 公理化-- と同じである. 現代数学では, このような思考の節約は多くの分野で有効であったが, それが数学の全てではない. 同じように計算機科学における Object 指向や抽象データ型の 概念( Java などで実現されている)は, 有効な局面も多くあったが, 万能というわけではない ことを注意しておこう.



Nobuki Takayama 平成15年9月12日