ユークリッド互除で合同式の問題を解く

質問

学校の課題でわからなかった所です。
mを法としてaとxが合同である、という問題を解いています。ax (三本線)b（mod m）
という合同式です。
ax-my=b=gcd(a,m)に直してｘを求めてます。
ｘが二乗になった時の解き方がわかりません。
わかりにくい質問ですみませんがお願いします。

回答No.1

yaksa

2次合同式
ax^2 ≡ b (mod m) を解けということですか。

ここで説明するのは大変なんで、キーワードを「」でくくっておくので、google等で検索してください。けっこう、有益な情報がたくさんみつかると思います。

とりあえず、x^2について1次合同式だと思って解くと
x^2 ≡ c (mod m)
になります。これを解けばいいんですが、
まず、法mが素数でないと厄介なんで、
「中国剰余定理」（「中国人剰余定理」）
を使って法が素数の合同式に分解します。

で、
x^2 = a (mod p)
の形を2次合同式を解くには、
「平方剰余」「平方非剰余」「ルジャンドルの記号」
といった概念が必要になるので、検索してください。