元祖ワシ的日記

一つ前のエントリでは

$$x^2 = a \pmod{p}$$

の解がわかると

$$x^2 = a \pmod{p^2}$$

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

$$(x-\sqrt{a})^k$$
を計算して
$\sqrt{a}$の係数が$\pmod{p^k}$で1になるように逆数を乗じればokです。

$\sqrt{a}$の係数が$p$で割り切れてしまうとまずいのでそのことだけ証明しないといけませんが、結論だけから言うとその係数は
$(2u)^{k-1}$に$\mod{p}$で等しくなります。つまり$u^2=a\pmod{p}$としたとき

$$(u_{k}-v_{k}\sqrt{a}) =(u-\sqrt{a})^k$$
とすると

$$v_k=(2u)^{k-1}\pmod{p}$$
となります。よって$v_k$は$p$と互いに素で、逆数が存在することになり解を求めることが出来ます。