Uso del símbolo de Legendre

Question

¿Cuáles son las soluciones? $x^{2} \equiv7 \mod{53}$ , $x^{2} \equiv53 \mod{7}$ , $x^{2} \equiv 14 \mod{31}$ , $x^{2} \equiv 25\mod{997}$ ?

Tengo todas estas propiedades para este símbolo de Legendre y ni idea de qué hacer con él para encontrar si éstas tienen solución, y mucho menos resolverlas si la tienen.

Answer 1

Todos tienen soluciones. Desde $53 \equiv 1 \pmod{4}$ tenemos

$$\left(\frac{7}{53}\right) = \left(\frac{53}{7}\right) = \left(\frac{4}{7}\right) = \left(\frac{2}{7}\right)^2 = 1,$$

que resuelve los dos primeros. $31 \equiv 7 \pmod{8}$ Así que

$$\left(\frac{14}{31}\right) = \left( \frac{2}{31}\right) \left(\frac{7}{31}\right) = \left(\frac{7}{31}\right) = - \left(\frac{31}{7}\right) = - \left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac13\right) = 1.$$

Y finalmente

$$\left(\frac{25}{997}\right) = \left(\frac{5}{997}\right)^2 = 1.$$

La búsqueda de soluciones es una cuestión diferente, pero

$$22^2 = 484 = 9\cdot 53 + 7;\quad 2^2 = 4 \equiv 53 \pmod{7};\quad 13^2 = 169 = 5\cdot 31 + 14; \quad 5^2 = 25.$$

Answer 2

Para la primera, queremos $(7/53)$ . Nuestros dos números son primos, y uno tiene la forma $4k+1$ . Así que por reciprocidad cuadrática, $(7/53)=(53/7)$ .

Pero $53\equiv 4\pmod 7$ Así que $(53/7)=(4/7)$ . Pero $4$ es un cuadrado perfecto, por lo que $(4/7)=1$ . De ello se desprende que $(7/53)=1$ Así que $x^2\equiv 7\pmod{53}$ tiene una solución.

Al mismo tiempo que resolvíamos el primer problema, solucionábamos el segundo. Vimos que $(53/7)=1$ , por lo que la congruencia $x^2\equiv 53\pmod{7}$ tiene una solución. Pero realmente necesitamos una maquinaria mínima para ello, ya que $53\equiv 4\pmod{7}$ por lo que la congruencia tiene las soluciones obvias $x\equiv \pm 2\pmod{7}$ .

Saltando hacia adelante, la congruencia $x^2\equiv 25\pmod{997}$ tiene al menos una solución obvia, sin necesidad de calcular el símbolo de Legendre.

Para la congruencia $x^2 \equiv 14\pmod{31}$ el enfoque de los símbolos de Legendre nos hace evaluar $(14/31)$ . Por una de las propiedades estándar de los símbolos de Legendre, esto es $(2/31)(7/31)$ .

Porque $31$ es un primo de la forma $8k+1$ tenemos $(2/31)=1$ . Ahora tenemos que evaluar $(7/31)$ . Dado que cada uno de $7$ y $31$ es un primo de la forma $4k+3$ por el argumento de la reciprocidad $(7/31)=-(31/7)$ . Pero $31\equiv 3\pmod{7}$ , por lo que queremos $-(3/7)$ . Por Reciprocidad, esto es el negativo del negativo de $(7/3)$ Así que es $(7/3)$ . Pero $(7/3)=(1/3)=1$ . Se deduce que la congruencia $x^2\equiv 14\pmod{31}$ tiene una solución.