Menemukan akar polinomial menggunakan timbal balik kuadrat

Aug 17 2020

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

MichaelRozenberg Aug 17 2020 at 18:39

$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Bisakah kamu mengakhirinya sekarang?

J.W.Tanner Aug 17 2020 at 18:41

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$

B.Goddard Aug 17 2020 at 19:44

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$.