アルゴリズム論特論(塩田)第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$ で割り切れること」を証明する。