Нахождение корней многочлена с помощью квадратичной взаимности
Полином $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$.