アルゴリズム論特論（塩田）　2015年度教材　第6回

授業内容
- 法 n での除算
- 剰余類
- 既約剰余類
- フェルマの小定理の別証明
- オイラーの定理
  - φ(n) = ( 法 n の既約剰余類の個数 ) とすると
    gcd(a, n) = 1 ⇒ 法 n で a ^φ(n) = 1
ツボ
- 法 n で a の逆数が存在すること ⇔ gcd(a, n) = 1
宿題
- 引数 a, n に対し、
  x = ( 法 n での a の逆数 )
  となる整数 x ( 0 ≦ x ＜ n ) を返り値とする関数 modinv を定義し、動作確認をせよ。