Pebble's Diary

プログラマーの作業メモ

mod p の世界では、割り算をべき乗計算に置き換えられる

フェルマーの小定理でpを素数とすると、mod pの世界では、割り算をべき乗に置き換えられます。
pを3以上の素数としておきます。
フェルマーの小定理
 b ^ { p -1 } = 1\mod p
で、pは3以上なので、
 b ^ { p - 2 } \times b = 1\mod p
と書けます。これは mod p においては、乗算に対して、bの逆元が  b ^ { p -2 }であることを示しています。
つまり、bで割り算をしたかったら、 b ^ { p - 2}で掛け算をすればよいわけです。
そういえば、少し前で  b ^ { e }\mod m を計算する関数を作りましたよね?
ここでズバリ割り算をする関数を作ります。関数名はinversemodとしておきます。

func inversemod(b:Int, p:Int) -> Int {
    return expmod(b, p - 2, p)
}