二次合同式の解き方

質問

二次合同式の解の求め方なんですが、たとえば次のような二次合同式に対して、mod3とmod9に分けて解を求める場合、どのように計算を行えばいいのでしょうか？
いろいろ調べてみたのですがいまいち解き方がわかりません。どなたかアドバイスをお願いします。

x^2 = 7 (mod27)

回答No.2

Mr_Holland

ANo.1は煩雑でした。
　もう少しスマートに計算することができましたので、以下に示します。

　x^2≡7 (mod 27)
⇒x^2≡7 (mod 9)
⇒x^2≡1 (mod 3)
⇔x≡±1 (mod 3)
∴x=3n±1　(n:整数）とおける。
　以下、複号同順とします。

　x^2=(3n±1)^2= 9n^2±6n+1 だから
　　x^2≡±6n+1≡7 (mod 9)
　∴±6n≡6 (mod 9)
　∴±2n≡2 (mod 3)

　この合同式は　±n=1 のとき成立するので　±n=3m+1　（m:整数）とおける。
　x^2=9(3m+1)^2+6(3m+1)+1 =81m^2+72m+16 だから
　　x^2≡18m+16≡7 (mod 27)
　∴18m+9≡0 (mod 27)
　∴2m+1≡0 (mod 3)

　この合同式は　m=1 のとき成立するので　m=3k+1　（k:整数）とおける。

　　x=3n±1=±(±3n+1)=±{3(3m+1)+1}=±(9m+4)=±{9(3k+1)+4}=±(27k+13)
　∴x≡±13 (mod 27)
　∴x≡13,14 (mod 27)

回答No.1

Mr_Holland

x^2 の法を　27,9,3 と変化させると次のようになります。

　　x^2≡7 (mod 27)　≡7 (mod 9) ≡1 (mod 3)

　3を法としたとき　平方数x^2 が1になるのは　xが3の倍数でないとき（x=3n±1, n:整数）だけです。
　（x^2=(3n±1)^2=9n^2±6n+1 となることから）

　ここで　x=3n±1 (n:整数)の平方数で　9を法とした数を考えます。
　　x^2=9n^2±6n+1 ≡±6n+1 ≡7 (mod 9)

　この合同式は　nの係数の符号が+のとき　n=1 のときに成立し、nの係数の符号が-のとき　この合同式は　n=2 のときに成立する。
　6と9の最小公倍数18を6で割ったものは3なので n は次のように表せます。
　　n=3m+1　(nの係数の符号が+のとき),
　　　3m+2　(nの係数の符号が-のとき）　　（m:整数）
　∴x=3(3m+1)+1=9m+4　(nの係数の符号が+のとき),
　　　=3(3m+2)-1=9m+5 (nの係数の符号が-のとき）
　∴x=9m+4, 9m+5

(1)　x=9m+4　のとき
　　x^2=(9m+4)^2=81m^2+72m+16
　　　　≡18m+16 ≡7 (mod 27)
　この合同式は　m=1 のとき成立し、18と27の最小公倍数54を18で割ったものは3なので m は次のように表せます。
　　m=3k+1　　（k:整数）
　∴x=9(3k+1)+4=27k+13

(2)　x=9m+5　のとき
　　x^2=(9m+5)^2=81m^2+90m+25
　　　　≡9m+25 ≡7 (mod 27)
　この合同式は　m=1 のとき成立し、9と27の最小公倍数27を9で割ったものは3なので m は次のように表せます。
　　m=3k+1　　（k:整数）
　∴x=9(3k+1)+5=27k+14

　以上をまとめて
　∴x≡13,14 (mod 27)