アルゴリズム論特論(塩田)第5回 (6) 今日のまとめ

今日のまとめ

  • 加法・減法・乗法・べき乗に関して、合同式はイコール感覚で使える。
  • 法が素数のときは、RSA 暗号の動作原理であるフェルマの小定理が成り立つ。

自宅学習の例

  • Ex.8 をまねて、$715 \times 46 = 32890$ の検算をする。
  • $10\,!$ を $11$ で割った余りを、合同式を使って求める。( ウィルソンの定理 )
  • 「10進数 $(x_n \cdots x_2x_1x_0)_{10}$ が $11$ で割り切れること
      $\Leftrightarrow$ $x_0 - x_1 + x_2 - x_3 + \cdots$ が $11$ で割り切れること」を証明する。