メニュー
ホーム
アーカイブ
元祖ワシ的日記
ほぼ雑記的メモ
←mod p^2における平方根
FreeBSDのswapファイルがうまく作成できなかったので調べてみた→
mod p^kにおける平方根
2023年11月16日(木)
一つ前のエントリでは
x
2
=
a
(
mod
p
)
の解がわかると
x
2
=
a
(
mod
p
2
)
を解くことが出来たのでした。同じ考え方で任意の
p
k
について次のようにして求めることが出来ます。
(
x
−
a
)
k
を計算して
a
の係数が
(
mod
p
k
)
で1になるように逆数を乗じればokです。
a
の係数が
p
で割り切れてしまうとまずいのでそのことだけ証明しないといけませんが、結論だけから言うとその係数は
(
2
u
)
k
−
1
に
mod
p
で等しくなります。つまり
u
2
=
a
(
mod
p
)
としたとき
(
u
k
−
v
k
a
)
=
(
u
−
a
)
k
とすると
v
k
=
(
2
u
)
k
−
1
(
mod
p
)
となります。よって
v
k
は
p
と互いに素で、逆数が存在することになり解を求めることが出来ます。
Tweet
エントリにコメントする
エントリにコメントする
タイトル
名前
コメント
完了
コメントが表示されるまで時間がかかることがあります。
Powered by
Red Leaf
( Rev. 79d0bae58 ), © Issei Numata, 2007-2025