İkinci dereceden karşılıklılık kullanarak bir polinomun köklerini bulma

Aug 17 2020

Polinom mu $X^2− X + 19$ kök salmak $\mathbb Z/61\mathbb Z$? Bu sorunun nasıl çözüleceğinden emin değilim, ancak aşağıdaki problemde bu sorunlara nasıl yaklaştığımı özetledim.

İkinci dereceden mi $X^2 -59$ kök salmak $\mathbb Z/61\mathbb Z$?

Şimdiye kadar yaptığım şey kendime sormak $59$ikinci dereceden bir kalıntıdır. Başka bir deyişle nedir$59/61$? Karşılıklı olarak sahibiz$59/61 = 61/51 = 10/51$ dan beri $61 ≡ 10\bmod51$. $10$ asal değildir, bu yüzden onu $(2/51)*(5/51).$ Fakat $2/51$ dır-dir $-1$ dan beri $3 ≡ 51\bmod8$. Böylece onu yeniden yazabiliriz$-1 * (5/51)$ve karşılıklılık ile $5/51 = 51/5 = 1/5$ dan beri $1 ≡ 51\bmod5$. Yani$-1*(5/51) = - (1/5) = -1 (1) = -1$, yani $x^2 - 59$ kökü yok.

Yanıtlar

MichaelRozenberg Aug 17 2020 at 18:39

$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Şimdi bitirebilir misin?

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

Kareyi tamamlayın.

$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$ veya $-12\bmod 61$

$X\equiv7$ veya $-6\bmod 61$

B.Goddard Aug 17 2020 at 19:44

İkinci dereceden çözmenin genel yolu kareyi tamamlamaktır. Eğer varsa$ax^2+bx+c \equiv 0 \pmod{p}$ kareyi tamamlamak sana verecek $y^2\equiv d \pmod{p},$ nerede $y = 2ax+b$ ve $d=b^2-4ac.$

İşin güzel tarafı $y$ orijinal sol tarafın türevidir ve $d$ikinci dereceden olağan ayırt edicidir. Yani sorunun için:

$y = 2x+1$ ve $d=1^2-4\cdot 19 = -75$.

Öyleyse $-75$ ikinci dereceden bir kalıntıdır, çözebilirsiniz $y$ ve sonra da çöz $x$.