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