アルゴリズム論特論（塩田）　2017年度教材

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

授業内容
- 除算と割り算の違い
  - a から b を何回取り除けるか、を数えるのが除算
  - a を b 等分しようとするのが割り算
- 有理数
  - 単位分数 1/b が「ある」ことにする ⇒ 余り無く a ÷ b ができる
  - rational number ( 比の数 ) を reasonable と勘違いして訳してしまった。
  - 間違いだったのだが、分数で書くことが無理な数 = 無理数 = 有理数でない数という話ともマッチして広く受け入れられた。
- 法演算での除算
  - bx ≡ 1 ( mod n ) が整数解 x をもつとき、b は mod n で逆数 x を持つ、と定義する。
  - b は mod n で逆数 x を持つこと ⇔ gcd(b, n) = 1
  - この x はユークリッドのアルゴリズムを用いて求める。
- 法演算での逆数の、手計算における工夫
  - 任意の法 n で, 1/1 = 1, 1/(n-1) = n-1
  - 法 n が奇数のとき 1/2 = (1+n)/2
  - 1/3 は
    - n = 3k+1 の形のとき 1/3 = (1+2n)/3
    - n = 3k+2 の形のとき 1/3 = (1+n)/3
  - b が小さいときは 1/b = (1+n)/b = (1+2n)/b = ... と書いていって、最初に割り切れたところが答え。( b回まわす間に必ず答えがある。)
ツボ
- 法演算での除算は、除数が法と互いに素なときのみ可能
- ユークリッドのアルゴリズムの応用により、法演算での除算の計算量は O(log²(n))