法が合成数の時の平方剰余

法が合成数の時の平方剰余
法が素数であれば平方剰余の相互法則等を用いて、
簡単に平方剰余の判定ができます。
http://ja.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9% …

では、法が合成数だった場合、簡単な計算方法はあるのでしょうか？

No.2 ベストアンサー 回答者： yoikagari 回答日時： 2010/07/18 16:10

このサイトに証明があるね。

http://aozoragakuen.sakura.ne.jp/suuron/node25.h …
でf(x)=x^2-aとすると君の問題の議論になるはず。

定理15でやっていることをかいつまんで説明すると
f(x)≡0 (mod p^k)が解をもつとき、f(x))≡0 (mod p^(k+1) )
の解がどうなるかということ。

x^2≡a (mod p)の解が分かれば、x^2≡a (mod p^k)の解が
構成できる。

定理16をかいつまんで説明すると
mをm=(p_1)^(k_1)・...・(p_r)^(k_r)と素因数分解したとき
f(x)≡0 (mod (p_1)^(k_1) )，…，f(x)≡0 (mod (p_r)^(k_r) )が共に解をもつならば
中国剰余定理を用いると、f(x)≡0 (mod m)も解をもつことが分かる
ということ。

定理16により、
mをm=(p_1)^(k_1)・...・(p_r)^(k_r)と素因数分解したとき
x^2≡a (mod (p_1)^(k_1) )，…，x^2≡a (mod (p_r)^(k_r) )が共に解をもつならば
x^2≡a (mod m)も解をもつことが分かる。

中国剰余定理およびその証明は
http://aozoragakuen.sakura.ne.jp/suuron/node24.h …
を参照のこと

この回答へのお礼

すばらしいです。ありがとうございます。
合同方程式の解法は検索したつもりだったのですが、
そしてご紹介いただいたサイトも知っていたのですが、
そのものずばりの解法が載ってますね。

お礼日時：2010/07/19 20:00

No.3 回答者： yoikagari 回答日時： 2010/07/18 16:18

x^2≡a (mod m)が整数解sを持つとき

整数kを用いてs^2-a=mkとかける。

mの約数dを任意に取るとm=dnと書ける
s^2-a=dnkとかけるから、x^2≡a (mod d)が解sを持つことがわかる。

とくにdが素数pの場合を考える
x^2≡a (mod m)が解を持てば、mの任意の素因数pに対して
x^2≡a (mod p)が解をもつことがわかる。

対偶をとれば
mのある素因数qに対してx^2≡a (mod q)が解を持たなければ
x^2≡a (mod m)が解を持たないこと

mの任意の素因数pに対してx^2≡a (mod p)が解をもてば
俺が先に書いた方法でx^2≡a (mod m)の解は構成できる。

No.1 回答者： koko_u_u 回答日時： 2010/07/18 11:02

ちょっと想像すると、話は逆だと思うんですよね。

『x^2 ≡ a ( mod m ) が解きたい。』

という問題意識が最初にあって、色々考えていくと m が素数のときに

『x^2 ≡ a ( mod p ) が解けるか？』

に問題が帰着して、最後に平方剰余の相互法則を得たんだと思います。

この回答へのお礼

歴史的には、おっしゃるとおりだと思います。
ただ検索のしかたが悪かったのか、
合同方程式の解法からどのように平方剰余までたどりついたのかの道筋が
見つからなかったので質問させていただきました。

お礼日時：2010/07/19 19:16