Trovare le radici di un polinomio usando la reciprocità quadratica
Fa il polinomio $X^2− X + 19$ avere una radice in $\mathbb Z/61\mathbb Z$? Non sono sicuro di come affrontare questo problema, ma ho delineato il modo in cui ho affrontato questi problemi nel problema seguente.
Fa il quadratico $X^2 -59$ avere una radice in $\mathbb Z/61\mathbb Z$?
Quello che ho fatto finora è chiedermi se $59$è un residuo quadratico. In altre parole, cos'è$59/61$? Per reciprocità abbiamo$59/61 = 61/51 = 10/51$ da $61 ≡ 10\bmod51$. $10$ non è primo, quindi lo prenderemo in considerazione come $(2/51)*(5/51).$ Ma $2/51$ è $-1$ da $3 ≡ 51\bmod8$. Quindi possiamo riscriverlo come$-1 * (5/51)$e per reciprocità $5/51 = 51/5 = 1/5$ da $1 ≡ 51\bmod5$. Così$-1*(5/51) = - (1/5) = -1 (1) = -1$, così $x^2 - 59$ non ha una radice.
Risposte
$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Puoi farla finita adesso?
Completa il quadrato.
$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$ o $-12\bmod 61$
$X\equiv7$ o $-6\bmod 61$
Il modo generale per risolvere la quadratica è completare il quadrato. Se hai$ax^2+bx+c \equiv 0 \pmod{p}$ quindi completare il quadrato ti darà $y^2\equiv d \pmod{p},$ dove $y = 2ax+b$ e $d=b^2-4ac.$
Il bello è quello $y$ è il derivato del lato sinistro originale e $d$è il solito discriminante del quadratico. Quindi per il tuo problema:
$y = 2x+1$ e $d=1^2-4\cdot 19 = -75$.
Quindi se $-75$ è un residuo quadratico, puoi risolvere $y$ e poi a sua volta risolvere per $x$.