ルジャンドルの記号 ❲ ❳
x^2≡a (mod p)において
解を持つ→❲a/p❳=1
解を持たない→❲a/p❳=-1
a=pt+b→❲a/p❳=❲b/p❳ : a＞pのとき利用
オイラーの規準
pを奇素数、aをpと互いに素な0でない整数
とする。
❲a/p❳≡a^{(p-1)/2}
pを奇素数とする。
第一補充法則 ❲-1/p❳=(-1)^{(p-1)/2}
第二補充法則 ❲2/p❳=(-1)^{(p^2-1)/8}
ルジャンドル記号の性質
a,bがpの倍数でないとき
❲(ab)/p❳=❲a/p❳×❲b/p❳
平方剰余の相互法則
相異なる奇素数p,qに対して
❲q/p❳×❲p/q❳=(-1)^{(p-1)/2×(q-1)/2}
本来はすべて証明すべきことだが、これらを利用して2次合同式の可解性について考える。
===============================
【ルジャンドル記号❲ ❳の計算ルール】
p,qを奇素数とする。
①❲1/p❳=1、❲k^2/p❳=1
②❲(pt+r)/p❳=❲r/p❳
③a,bがpの倍数でないとき、
❲(ab)/p❳=❲a/p❳×❲b/p❳
④p=4s+3, q=4t+3→❲q/p❳=-❲p/q❳
それ以外→❲q/p❳=❲p/q❳
⑤p=8k±1→❲2/p❳=1, p=8k±3→❲2/p❳=-1
===============================
【❲a/p❳を計算アルゴリズム】
①a＞pのとき、a=pt+r→❲a/p❳=❲r/p❳
②aが合成数のとき、素因数分解する。
a=Π(p[i]^t[i]), t[i]≡u[i] (mod 2)
❲a/p❳=Π❲p[i]/p❳^u[i]
③p[i]すべてが2のとき→⑤
以下p[i]≠2を、処理する。
④p=4k+3, p❲i❳=4k+3のとき、
❲p[i]/p❳=-❲p/p[i]❳
それ以外のとき、❲p[i]/p❳=❲p/p[i]❳
①に戻る
⑤❲a/p❳を(-1)^s×Π❲2/q[i]❳の形に変形する。
⑥q[i]=8k±3である個数をtとする。
⑦❲a/p❳=(-1)^(s+t)
【例】x^2≡24 (mod 83)
❲24/83❳
24=2^3×3より、3≡1 (mod 2)
❲24/83❳=❲2/83❳×❲3/83❳
3=4×0+3, 83=4×20+3→❲3/83❳=-❲83/3❳
❲24/83❳=❲2/83❳×(-❲83/3❳)=-❲2/83❳×❲83/3❳
83=3×27+2→❲83/3❳=❲2/3❳
❲24/83❳=-❲2/83❳×❲2/3❳
3,83ともに8k±3型
❲24/83❳=-(-1)^2=-1
よって、解なし
【例】x^2≡42 (mod 89)
❲42/89❳
42=2×3×7
❲42/89❳=❲2/89❳×❲3/89❳×❲7/89❳
=❲2/89❳×❲89/3❳×❲89/7❳
=❲2/89❳×❲1/3❳×❲5/7❳
=❲2/89❳×1×❲7/5❳
=❲2/89❳×❲2/5❳
=1×1=1
よって、解あり
x≡24,65 (mod 89)→次回解説
【注意】(mod 2)の2次合同方程式
①x^2+x+1≡0 (mod 2)
②x^2+x≡0 (mod 2)
③x^2+1≡0 (mod 2)
④x^2≡0 (mod 2)
①x^2+x+1≡0 (mod 2)
x^2+x≡1→x(x+1)≡1
x(x+1)は常に偶数だから、x(x+1)≡0
よって、解なし
②x^2+x≡0→x(x+1)≡0→x≡0,-1
→x≡0,1→すべての整数
③x^2+1≡0 (mod 2)→x^2≡1→x≡±1
→x≡1→xは奇数
④x^2≡0 (mod 2)→x≡0→xは偶数
(2022/10/31・11/14)
