Encontrando raízes de um polinômio usando reciprocidade quadrática

Aug 17 2020

O polinômio $X^2− X + 19$ tem uma raiz em $\mathbb Z/61\mathbb Z$? Não tenho certeza de como lidar com esse problema, mas esbocei a maneira como tenho abordado esses problemas no problema abaixo.

Faz o quadrático $X^2 -59$ tem uma raiz em $\mathbb Z/61\mathbb Z$?

O que tenho feito até agora é me perguntar se $59$é um resíduo quadrático. Em outras palavras, o que é$59/61$? Por reciprocidade temos$59/61 = 61/51 = 10/51$ Desde a $61 ≡ 10\bmod51$. $10$ não é primo, então vamos fatorá-lo como $(2/51)*(5/51).$ Mas $2/51$ é $-1$ Desde a $3 ≡ 51\bmod8$. Então, podemos reescrever como$-1 * (5/51)$, e por reciprocidade $5/51 = 51/5 = 1/5$ Desde a $1 ≡ 51\bmod5$. então$-1*(5/51) = - (1/5) = -1 (1) = -1$, então $x^2 - 59$ não tem raiz.

Respostas

MichaelRozenberg Aug 17 2020 at 18:39

$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Você pode terminar agora?

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

Complete o quadrado.

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

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

B.Goddard Aug 17 2020 at 19:44

A maneira geral de resolver quadráticas é completar o quadrado. Se você tem$ax^2+bx+c \equiv 0 \pmod{p}$ então completar o quadrado lhe dará $y^2\equiv d \pmod{p},$ Onde $y = 2ax+b$ e $d=b^2-4ac.$

O bom é que $y$ é a derivada do lado esquerdo original e $d$é o discriminante usual do quadrático. Então, para o seu problema:

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

Então se $-75$ é um resíduo quadrático, você pode resolver para $y$ e então resolver para $x$.