Menemukan akar polinomial menggunakan timbal balik kuadrat
Apakah polinomial $X^2− X + 19$ berakar $\mathbb Z/61\mathbb Z$? Saya tidak yakin bagaimana cara mengatasi masalah ini, tetapi saya menguraikan cara saya mendekati masalah ini dalam masalah di bawah ini.
Apakah kuadrat $X^2 -59$ berakar $\mathbb Z/61\mathbb Z$?
Apa yang telah saya lakukan sejauh ini adalah bertanya pada diri saya sendiri $59$adalah residu kuadrat. Dengan kata lain apa itu$59/61$? Dengan timbal balik yang kita miliki$59/61 = 61/51 = 10/51$ sejak $61 ≡ 10\bmod51$. $10$ bukan bilangan prima jadi kami akan memfaktorkannya sebagai $(2/51)*(5/51).$ Tapi $2/51$ adalah $-1$ sejak $3 ≡ 51\bmod8$. Jadi kita bisa menulis ulang sebagai$-1 * (5/51)$, dan dengan timbal balik $5/51 = 51/5 = 1/5$ sejak $1 ≡ 51\bmod5$. Begitu$-1*(5/51) = - (1/5) = -1 (1) = -1$, jadi $x^2 - 59$ tidak memiliki root.
Jawaban
$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Bisakah kamu mengakhirinya sekarang?
Selesaikan persegi.
$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$ atau $-12\bmod 61$
$X\equiv7$ atau $-6\bmod 61$
Cara umum untuk menyelesaikan kuadrat adalah dengan menyelesaikan kuadrat. Jika Anda memiliki$ax^2+bx+c \equiv 0 \pmod{p}$ maka menyelesaikan kotak akan memberi Anda $y^2\equiv d \pmod{p},$ dimana $y = 2ax+b$ dan $d=b^2-4ac.$
Yang menyenangkan adalah itu $y$ adalah turunan dari sisi kiri asli dan $d$adalah diskriminan kuadrat biasa. Jadi untuk masalah Anda:
$y = 2x+1$ dan $d=1^2-4\cdot 19 = -75$.
Jadi jika $-75$ adalah residu kuadrat, yang bisa Anda pecahkan $y$ dan kemudian pada gilirannya memecahkan $x$.