mod p^kにおける平方根

一つ前のエントリでは

x2=a(modp)

の解がわかると

x2=a(modp2)

を解くことが出来たのでした。同じ考え方で任意のpkについて次のようにして求めることが出来ます。

(xa)k
を計算して
aの係数が(modpk)で1になるように逆数を乗じればokです。

aの係数がpで割り切れてしまうとまずいのでそのことだけ証明しないといけませんが、結論だけから言うとその係数は
(2u)k1modpで等しくなります。つまりu2=a(modp)としたとき

(ukvka)=(ua)k
とすると

vk=(2u)k1(modp)
となります。よってvkpと互いに素で、逆数が存在することになり解を求めることが出来ます。
Posted by issei

カテゴリ : 数学