数論基礎特論（Elementary Number Theory）[1304]

＜授業のねらい及び具体的な到達目標＞

Mathemactica, Maple等いわゆる数式処理に用いられる整数計算アルゴリズムの基本を即ち、Euclidの互除法，連立一次合同式，中国剰余の定理，二次合同式，平方剰余の理論を理解する。これらの定理がいかにして具体的な計算応用できるか，その計算効率はどの程度かを考える。また同じ計算でも数学の深い定理を用いると計算速度が格段に速くなることを理解する。

＜授業計画及び準備学習＞

まず計算における速さ，即ち計算量というものを定義し多項式時間で計算できないと実用的でないことを解説する。さらに商と剰余を厳密に定義し最大公約数，最小公倍数を定義する。これらの値の多項式時間での計算にEuclidの互除法が重要であることを示す。また自明なような合同式の定義からFermat，Wilson，Eulerの各定理のような重要なものが得られることを詳述する。最後に現代整数論のはじまりとなった二次合同式とGaussの平方剰余の定理を述べる。
　
１　自然数の定義と整数、計算量について
２　三則、商と余り
３　公約数、公倍数、最大公約数、最小公倍数
４　最大公約数の求め方、Euclidの互除法とその計算量
５　合同式の定義と計算
６　群の定義とその例
８　剰余群の定義とその性質　
９　一次合同式
１０　連立一次合同式とChinese　Remainder　Theorem
１１　連立一次方程式の解法　基本的な解法,Gaussの方法、Garnerの方法
１２　2次合同式の解法　いくつかの例
１３　Legendreの記号の定義とその性質
１４　平方剰余の相互法則　計算法と例
１５　相互法則の証明

準備学習は以下のとおり
　講義中出した問題を考えておくこと。また教科書等の該当する箇所を読んでおくこと。

＜成績評価方法及び水準＞

レポート問題の提出によって評価する。内容の間違っているものは返却しどの点が不十分か解説し再提出を求める。（再提出、再々提出して正解なら評価の対象となる）またレポート問題にはプログラム作成（作譜）もありC言語等に習熟していればこれらの面でも評価する。

＜教科書＞

“U-Basicによるコンピュータ整数論”木田，牧野　日本評論社
この本は絶版なのでこの内容をデータ化したもの
http://trex.cc.kogakuin.ac.jp/master1/Number_Theory.pdf
をダウンロードして印刷してください。

＜参考書＞

“初等整数論講義”高木貞治　共立出版

＜オフィスアワー＞

月曜日　午前11時から12時　新宿校舎27階数学研究室または講義終了後

＜学生へのメッセージ＞

レポート問題の中にはかなり大変なものもあるので１，２回でへこたれず何度も手直して提出してください。