Autor Tema: Problema con números primos

0 Usuarios y 1 Visitante están viendo este tema.

04 Abril, 2008, 10:49 pm
Leído 1294 veces

Velmat

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 6
  • Karma: +0/-0
1. Si p es un primo de la forma \(  4n-3  \) demuestre que no se puede resolver \(  x^2 \equiv (-1) \pmod{p} \)
2. Demuestre que si p es un primo de la forma \(  4n-1  \) entonces se puede resolver \(  x^2 \equiv (-1) \pmod{p} \) (siendo x un entero)
3. Demuestre que si p es un primo de la forma \(  4n-1  \) y si \(  y = \left( \displaystyle\frac{(p-1)}{2} \right) ! \) entonces \(  y^2 \equiv (-1) \pmod{p} \)

05 Abril, 2008, 04:52 am
Respuesta #1

almendra

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 614
  • Karma: +0/-0
  • Sexo: Femenino
Hola.

Antes que nada, para que los enunciados sean correctos hay que intercambiar \( 4n-1 \) con \( 4n-3 \) en todos sus apariciones. O sea: 


1. Si p es un primo de la forma \(  4n -1  \) demuestre que no se puede resolver \(  x^2 \equiv (-1) \pmod{p} \)

2. Demuestre que si p es un primo de la forma \(  4n -3  \)  ( o \( 4n+1 \)) entonces se puede resolver \(  x^2 \equiv (-1) \pmod{p} \)
3. Demuestre que si p es un primo de la forma \(  4n -3  \) y si \(  y = \left( \displaystyle\frac{(p - 1)}{2} \right) ! \) entonces \(  y^2 \equiv (-1) \pmod{p} \)



Primera opción:  ¿puedes usar el símbolo de Legendre? Utilizando las propiedades de este símbolo, 1 y 2  se pueden hacer fácilmente.

Segunda opción: (un poco más a pulmón)

Empezamos por  3:  supongamos que  \( p=4n+1 \)  (que es lo mismo que  4n-3)      usamos el teorema de Wilson, que dice que si \( p \) es primo, entonces \( (p-1)!\equiv (-1) \pmod{p} \)
 
O sea, \( (p-1)\cdot (p-2)\cdot (p-3) \ldots  \left( \displaystyle\frac{(p - 1)}{2} \right) \ldots   3\cdot2\cdot 1  \equiv (-1) \pmod{p} \).

Observemos que   \( p-1 \equiv -1   \);  \( p-2 \equiv -2 \), ....  etc. de modo que, agrupando, queda:


 
  \( (-1) ^{\displaystyle\frac{p-1}{2}}  \left( \left( \displaystyle\frac{(p - 1)}{2} \right) !\right) ^2     \equiv (-1) \pmod{p} \) 


Como \( p=4n+1 \), entonces \( \displaystyle\frac{p-1}{2} \) es par, y \( (-1) ^{\displaystyle\frac{p-1}{2}}=1 \), y entonces la ecuación anterior queda    \(   \left( \left( \displaystyle\frac{(p - 1)}{2} \right) !\right) ^2     \equiv (-1) \pmod{p} \) 

Es decir, que vale 3.

Como consecuencia de esto, si \( p \) es de la forma \( 4n-3 \), la ecuación \(  x^2 \equiv (-1) \pmod{p} \)

tiene solución, es decir que vale 2.

Ahora, para probar 1, supongamos que \( p \) es de la forma \( 4n+3 \) (o \( 4n-1 \), que es lo mismo).

Entonces, utilizando el pequeño  teorema de Fermat,  tenemos que si \( x \)  es coprimo con p, entonces

\( x^{(p-1)}\equiv 1 \pmod{p} \).

Como \( p=4n+3 \), entonces esto queda   \( x^{4n+2}\equiv 1 \pmod{p} \), o sea \( (x^2)^{2n+1}\equiv 1 \pmod{p} \). Como \( 2n+1 \)  es un número impar,  y (-1) elevado a cualquier potencia impar da (-1),   de aquí podemos concluir que   \( x^2 \)  no es congruente con (-1) (mod p)   para ningún   valor de x.