アルゴリズム論特論（塩田）第6回 (7) 今日のまとめ
今日のまとめ
- 法演算の除算は、逆数を先に定義してから考える。
- 法 $n$ と互いに素な数 $b$ だけが逆数を持つ。
- 逆数は、拡張ユークリッドアルゴリズムを応用して求められる。
自宅学習の例
法 $11$ では、$2$ から $9$ が互い逆数になるペアに分かれて
$2 \times 6 \equiv 3 \times 4 \equiv 5 \times 9 \equiv 7 \times 8 \equiv 1$
となっています。このことから
$10\,! \equiv ( 2 \times 6 ) \times ( 3 \times 4 ) \times ( 5 \times 9 ) \times ( 7 \times 8 ) \times 10 \equiv 10 \pmod{11}$
が導かれます。
では、法が素数 $p$ のとき、同じ考え方で「ウィルソンの定理」
$(p-1)\,! \equiv (p-1) \quad\pmod p$
を導いてみましょう。