計算機数学I（第11回）

今回は、前回のEuclid互除法で残ったアルゴリズム自体の説明を行ってから、拡張Euclid互除法の説明を行いました。拡張Euclid互除法の根拠となる定理の証明は、時間の都合で、最も重要な「余因子の存在と計算手順」の部分のみを行いましたが、それ以外の証明も、一通り、講義ノートに記録しています。

この授業も残すところあとわずかですが、残りの時間は、（拡張）Euclidの互除法に関連する話題に充てる予定です。今回は、連分数展開の計算について説明しました。正則連分数の計算の際、Euclidの互除法が用いられます。これに関連し、ある条件を満たす無理数が、循環する連分数に展開されることも説明し、その計算も行いました。実は、連分数展開からもとの有理数や無理数を計算するのも（拡張）Euclidの互除法と関連性がありますが、こちらの方は時間の都合で割愛しました。

次回以降は、法逆元の計算と、これに関連して、中国剰余定理を（時間があれば）扱う予定です。

授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015