Recherche des racines d'un polynôme à l'aide de la réciprocité quadratique

Question

Le polynôme $X^2− X + 19$ avoir une racine dans $\mathbb Z/61\mathbb Z$? Je ne suis pas sûr de savoir comment résoudre ce problème, mais j'ai décrit la manière dont j'ai abordé ces problèmes dans le problème ci-dessous.

Est-ce que le quadratique $X^2 -59$ avoir une racine dans $\mathbb Z/61\mathbb Z$?

Ce que j'ai fait jusqu'ici, c'est me demander si $59$est un résidu quadratique. En d'autres termes, qu'est-ce que$59/61$? Par réciprocité nous avons$59/61 = 61/51 = 10/51$ depuis $61 ≡ 10\bmod51$. $10$ n'est pas premier, nous allons donc le factoriser comme $(2/51)*(5/51).$ Mais $2/51$ est $-1$ depuis $3 ≡ 51\bmod8$. Nous pouvons donc le réécrire comme$-1 * (5/51)$, et par réciprocité $5/51 = 51/5 = 1/5$ depuis $1 ≡ 51\bmod5$. Alors$-1*(5/51) = - (1/5) = -1 (1) = -1$, alors $x^2 - 59$ n'a pas de racine.

Answer 1

$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ Pouvez-vous y mettre fin maintenant?

Answer 2

Complétez le carré.

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

Answer 3

La manière générale de résoudre les quadratiques est de compléter le carré. Si tu as$ax^2+bx+c \equiv 0 \pmod{p}$ puis compléter le carré vous donnera $y^2\equiv d \pmod{p},$ où $y = 2ax+b$ et $d=b^2-4ac.$

Le plus gentil est que $y$ est le dérivé du côté gauche d'origine et $d$est le discriminant habituel du quadratique. Donc pour votre problème:

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

Donc si $-75$ est un résidu quadratique, vous pouvez résoudre pour $y$ puis à son tour résoudre pour $x$.