【2次合同方程式の解法②】
pを奇素数、aはpの倍数でないとする。
ax^2+bx+c≡0 (mod p)
❶a=1→x^2+bx+c≡0 (mod p)のとき
【Step1】1次の係数bが偶数b=2s
x^2+2sx+c≡0 (mod p)
x^2+2sx+s^2≡s^2-c
(x+s)^2≡s^2-c→[平方完成]
s^2-c≡t^2 (mod p)となるt
存在しないときは、解なし
【可解性】を参照
(x+s)^2≡t^2
x+s≡±t
x≡-s+t,-s-t (mod p)
【Step2】1次の係数 bが奇数
x^2+bx+c≡0
b+p, b-pは偶数→[1次の係数を偶数に]
x^2+(b+p)x+c≡0→【Step1】へ
❷a≠1→ax^2+bx+c≡0 (mod p)
【Step3】[a→1にする]
ay≡1 (mod p)→y≡k
akx^2+kbx+kc≡0
x^2+Bx+C≡0 (mod p)型
→【Step1】or【Step2】
【例】x^2-2x-9≡0 (mod 13)
x^2-2x+1≡10
(x-1)^2≡10
(x-1)^2≡10+13×2≡36≡6^2
x-1≡±6
x≡7, -5 (mod 13)
【例】x^2+3x+16≡0 (mod 13)
x^2-10x+16≡0
(x-5)^2≡9≡3^2
x-5≡±3
x≡8,2 (mod 13)
【例】2x^2+9x-10≡0 (mod 17)
2y≡1 (mod 17)→y≡9
18x^2+81x-90≡0
x^2+13x-5≡0
x^2-4x+4≡9
(x-2)^2≡3^2
x-2≡±3
x≡5,16 (mod 17)
【例】3x^2-5x+5≡0 (mod 11)
3y≡1 (mod 11)→y≡4
12x^2-20x+20≡0
x^2+2x-2≡0
x^2+2x+1≡3
(x+1)^2≡3+11×3≡36≡6^2
x+1≡±6
x≡5,4 (mod 11)
(2022/11/4)
