Otras carreras Determinar si tiene solución la congruencia (dependiendo si es resto cuadrático o no)

[cristianoceli]

Hola, tengo dudas con este ejercicio.


Usando $a^{\displaystyle\frac{p-1}{2}}\equiv{\pm{1}}$ determinar cuantas soluciones tienen las siguientes congruencias.


a) $x^2\equiv{5}$ $(mod$ $73)$


b) $x^2\equiv{3}$ $(mod$ $73)$


Bueno para que tenga solución la congruencia debe cumplirse que $a$ sea resto cuadrático, es decir, debe cumplirse que:


$a^{\displaystyle\frac{p-1}{2}}\equiv{1}$ $(mod$ $p)$

Si no tiene solución se cumple que

$a^{\displaystyle\frac{p-1}{2}}\equiv{-1}$ $(mod$ $p)$


Entonces veamos el ejercicio a si $a$ es resto cuadrático para ver si la congruencia tiene solución


$5^{\displaystyle\frac{73-1}{2}}\equiv{1}$ $(mod$ $73)$


$5^{\displaystyle\frac{72}{2}}\equiv{1}$ $(mod$ $73)$


$5^{36}\equiv{1}$ $(mod$ $73)$


Entonces debo ver si se cumple o no que $73|5^{36}-1$ y si no lo divide no es resto cuadrático


Lo que sucede es que no sé como probarlo ya que son números muy grandes y estoy atascado.


Para el ejercicio b es la misma idea solo debo ver si cumple $73|3^{36}-1$ pero también estoy atascado y no se que mas hacer.



Pd: El solucionario del libro dice que la congruencia a) no tiene solución lo que implicaria que 5 no es resto cuadrático modulo 73 y que la congruencia b si tiene solución, por lo tanto 3 es resto cuadratico modulo 73

Saludos

[Weip]

Re: Determinar si tiene solución la congruencia (dependiendo si es resto cuadrático o no)

Entonces debo ver si se cumple o no que $73|5^{36}-1$ y si no lo divide no es resto cuadrático


Lo que sucede es que no sé como probarlo ya que son números muy grandes y estoy atascado.

Pero ¿no te dejan calculadora?

Usando $a^{\displaystyle\frac{p-1}{2}}\equiv{\pm{1}}$ determinar cuantas soluciones tienen las siguientes congruencias.

Imagino que es un despiste pero recuerda que es una congruencia módulo $p$. En ejercicios para entregar o examenes ten presente que el módulo lo has de poner siempre.

[cristianoceli]

Re: Determinar si tiene solución la congruencia (dependiendo si es resto cuadrático o no)

Pero ¿no te dejan calculadora?


Imagino que es un despiste pero recuerda que es una congruencia módulo $p$. En ejercicios para entregar o examenes ten presente que el módulo lo has de poner siempre.

No, en el examen no me dejan calculadora y no se me ocurre como demostrarlo (Tendré presente el despiste)

Saludos

[Weip]

Re: Determinar si tiene solución la congruencia (dependiendo si es resto cuadrático o no)

Se me ocurren formas de hacer el ejercicio usando varias manipulaciones con los símbolos de Legendre que dan lugar a cálculos con números bajos pero si solo te dejan usar el criterio de Euler y nada más pues la verdad es que no sé cómo se resolverá. De todas formas te dejo este pdf, página 13, que contiene algunos ejemplos. Pero lo dicho, no es el criterio de Euler estrictamente. Ahora que me fijo solo te piden cuántas soluciones hay pero no te pide que las encuentres, así que eso puede ser una pista a tener en cuenta.

[cristianoceli]

Re: Determinar si tiene solución la congruencia (dependiendo si es resto cuadrático o no)

Si solo me dejan ocupar ese criterio. En otros ejercicio me piden que lo resuelva usando el símbolo de jacobi que me es mas sencillo

[Weip]

Re: Determinar si tiene solución la congruencia (dependiendo si es resto cuadrático o no)

Si solo me dejan ocupar ese criterio. En otros ejercicio me piden que lo resuelva usando el símbolo de jacobi que me es mas sencillo

Entonces lo siento, no te puedo ayudar. Igual si más tarde se me ocurre algo pues me paso por aquí y te lo digo. Si no es posible que otro usuario pueda ayudarte.