合同式の解き方を教えてください。

質問

解き方が別の合同式だと思うのですが、それぞれの問題の解き方を教えてください。

一つ目
次の合同式を解く、または、解けないことを証明せよ。

(a) 3x^2 - 5x + 7 ≡ 0 (mod 13)
(b) 5x^2 - 6x + 2 ≡ 0 (mod 13)
(c) x^2 + 7x + 10 ≡ 0 (mod 11)

二つ目
29の原始根は2であり、指数表を作り、それを使って合同式を解け。

(d) 17x^2 - 3x + 10 ≡ 0 (mod 29)
(e) x^7 ≡ 17 (mod 29)

これらの問題の解き方を教えてください。
よろしくお願いします。

回答No.1

ramayana · ベストアンサー

（一つ目）

法が13とか11のように小さい数なので、xの値が13ないし11種類しかありません。それらの値を順に代入して方程式を満たすかどうか確かめれば、終わりです。

もう少しスマートなやり方がお望みなら、別の方法もあります。法が素数の２次方程式は、普通に根の公式が使えることに注意しましょう。すなわち、

ax^2 + bx + c≡ 0 (mod p)　（p は素数。 a は、 mod p で0でない。）

の解は、次のようになります（ p > 2 なら、pを法とする２次方程式の解は、2 個存在するか、まったく存在しないかのどちらかです）。

*********

D = b^2 - 4ac と置く（D は、いわゆる判別式）。

もし、Dが mod p で平方数なら、D ≡ w^2 mod p として、解は、x ≡ (-b ± w)(2a)^(-1) mod pである。Dが mod p で平方数でなければ、解は存在しない。

*********

ちなみに、pがすごく大きい素数のときは、Dが mod p で平方数かどうかを判断する手法として、「平方剰余の法則」というのがあります。

（二つ目）

(d) については、一つ目と同じことです。ただ、原始根が2だと分かっているので、次のようにします： D ≡ 2^m mod 29 となる m を求める。mが奇数なら、解は存在しない。m が偶数なら、w = 2^(m/2) とする。

(e) については、次のとおり：17 ≡ 2^m mod 29 となる m をすべて求める（一般には、mが複数あることもある）。そのうち、7の倍数であるmが存在するなら、x = 2^(m/7) とする（解が複数あることもある）。

お礼

回答ありがとうございます。
これを見ながら問題を解いてみたいと思います。

回答No.2

ramayana

ANo.1の二つ目で間違いがあったので、修正します。

(d) について

m を、mod 28 で求める（28 = 29 - 1）。

(e) について

m を、mod 28 で求める。mは、ただ１つ定まる。
たまたま、28が7で割り切れる（28 = 4×7）ので、次の手順になる：

mが7で割り切れるか確かめる。.
m が7で割り切れないときは、解が存在しない。
m が7で割り切れるときは、n ≡ m/7 mod 4 となるnを mod 28 で求める（nは、7個あるはず）。x ≡ 2^n mod 29 が解（解は7個あるはず）。

（(e) は、言葉で書くと複雑に見えますが、実際に手を動かして計算すると、納得できると思います。）