平方剰余の相互作用を使用して多項式の根を見つける
多項式はありますか $X^2− X + 19$ にルーツを持っている $\mathbb Z/61\mathbb Z$？この問題をどのように解決するかはわかりませんが、以下の問題でこれらの問題に取り組む方法の概要を説明しました。
二次式はありますか $X^2 -59$ にルーツを持っている $\mathbb Z/61\mathbb Z$？
私がこれまでにしたことは、 $59$は平方剰余です。言い換えれば、何ですか$59/61$？相互主義によって私たちは持っています$59/61 = 61/51 = 10/51$ 以来 $61 ≡ 10\bmod51$。 $10$ 素数ではないので、次のように因数分解します $(2/51)*(5/51).$ だが $2/51$ です $-1$ 以来 $3 ≡ 51\bmod8$。だから私たちはそれを次のように書き直すことができます$-1 * (5/51)$、そして相互主義によって $5/51 = 51/5 = 1/5$ 以来 $1 ≡ 51\bmod5$。そう$-1*(5/51) = - (1/5) = -1 (1) = -1$、 そう $x^2 - 59$ ルートがありません。
回答
$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ 今すぐ終わらせてもらえますか？
正方形を完成させます。
$X^2-X+19\equiv0\bmod61\iff 4X^2-4X+76\equiv0\bmod61$
$\iff (2X-1)^2\equiv-75\equiv47\equiv169=13^2\bmod61$
$2X-1\equiv\pm13\bmod61$
$2X\equiv 14$ または $-12\bmod 61$
$X\equiv7$ または $-6\bmod 61$
二次方程式を解く一般的な方法は、正方形を完成させることです。あなたが持っている場合$ax^2+bx+c \equiv 0 \pmod{p}$ その後、正方形を完了すると、 $y^2\equiv d \pmod{p},$ どこ $y = 2ax+b$ そして $d=b^2-4ac.$
いいところは $y$ 元の左側の導関数であり、 $d$二次の通常の判別式です。だからあなたの問題のために：
$y = 2x+1$ そして $d=1^2-4\cdot 19 = -75$。
だからもし $-75$ は平方剰余であり、次のように解くことができます。 $y$ そして次に解決する $x$。