26 Febrero, 2020, 16:53 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: 1 ... 3 4 [5]   Ir Abajo
  Imprimir  
Autor Tema: UTF N=3; esbozo de ataque.  (Leído 5644 veces)
0 Usuarios y 2 Visitantes están viendo este tema.
Fernando Moreno
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 260


Ver Perfil
« Respuesta #80 : 22 Diciembre, 2019, 10:55 »

Hola. Quizás exista una manera alternativa de demostrar el Teorema de Wilson. Os lo propongo como tarea (y esta no se puede buscar por internet -que yo sepa). Yo lo voy a intentar también, pero conozco mis limitaciones. Supongo que hay que utilizar Teoría de Grupos.

Haciendo números me doy cuenta de lo siguiente:

Para todo primo impar  [texx]p[/texx] :

1.  [texx](p-1)^{(impar)}\equiv\,p-1[/texx] mod p .

2.  [texx](p-1)^{(par)}\equiv\,1[/texx] mod p .

No sé cuál es la explicación. Se cumple también creo para compuestos impares.

Y ahora tenemos lo siguiente (haciendo números también):

1.  Si  [texx](p-1)¡[/texx]  para  [texx]p\equiv\,1[/texx] mod 4 .  Encontraremos  [texx]\dfrac{p-1}{4}[/texx]  parejas congruentes con  [texx]p-1[/texx] .  Como este número de parejas es impar y el resto de parejas que quedan, multiplicadas entre sí, son congruentes con 1 Módulo  [texx]p[/texx] .  Entonces el resultado será congruente con  [texx]p-1[/texx]  elevado a un número impar y la conclusión es la que dice el Teorema de Wilson: Que   [texx](p-1)¡[/texx]  será congruente con  [texx]p-1[/texx]  Módulo  [texx]p[/texx] .

2.  Si  [texx](p-1)¡[/texx]  para  [texx]p\equiv\,3[/texx] mod 4 .  Nos encontraremos con  [texx]\dfrac{p-1}{2}[/texx]  parejas congruentes con  [texx]p-1[/texx] (todas las parejas posibles). Luego el conjunto de números será congruente con  [texx]p-1[/texx]  elevado a un número impar y el resultado será el del Teorema de Wilson.

Dicho con los vulgares números:

1.  Sea:  [texx]12¡=12\cdot{}11\cdot{\,}10\cdot{\,}9\cdot{\,}8\cdot{\,}7\cdot{\,}6\cdot{\,}5\cdot{\,}4\cdot{\,}3\cdot{\,}2\cdot{\,}1[/texx] .  Entonces:  [texx]12\cdot{1}[/texx]  ,  [texx]6\cdot{2}[/texx]   [texx]\wedge[/texx]   [texx]4\cdot{3}[/texx]  son congruentes con 12 Módulo 13. Y el resto de números multiplicados entre sí:  [texx]11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 5\equiv\,1[/texx] mod 13 . Luego:  [texx]12¡\equiv\,12^3\cdot 1[/texx] mod 13  [texx]\wedge[/texx]  [texx]12¡\equiv\,12[/texx] mod 13 .

2.  Sea:  [texx]10¡=10\cdot{\,}9\cdot{\,}8\cdot{\,}7\cdot{\,}6\cdot{\,}5\cdot{\,}4\cdot{\,}3\cdot{\,}2\cdot{\,}1[/texx] .  Entonces:  [texx]10\cdot{1}[/texx]  ,  [texx]9\cdot{6}[/texx]  ,  [texx]8\cdot{4}[/texx]  ,  [texx]7\cdot{3}[/texx]   [texx]\wedge[/texx]   [texx]5\cdot{2}[/texx]  son congruentes con 10 Módulo 11. Y  [texx]10¡\equiv\,10^5[/texx] mod 11  [texx]\wedge[/texx]  [texx]10¡\equiv\,10[/texx] mod 11 .  Como dice el Teorema de Wilson.


Espero vuestras respuestas. Saludos,
En línea

  El mal es malo también para sí mismo. Por eso, a la larga, sólo puede triunfar el bien. Y por eso también la libertad es buena y deseable..  F. Moreno 
Fernando Moreno
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 260


Ver Perfil
« Respuesta #81 : 22 Diciembre, 2019, 13:13 »

Hola,

Haciendo números me doy cuenta de lo siguiente:

Para todo primo impar  [texx]p[/texx] :

1.  [texx](p-1)^{(impar)}\equiv\,p-1[/texx] mod p .

2.  [texx](p-1)^{(par)}\equiv\,1[/texx] mod p .

No sé cuál es la explicación. Se cumple también creo para compuestos impares.

De esto ya me he dado cuenta. ¡Qué tonto! Como  [texx]p-1\equiv\,-1[/texx] mod p. Entonces es lo mismo que decir que:  [texx](-1)^{impar}=-1[/texx] mod p   [texx]\wedge[/texx]   [texx](-1)^{par}=1[/texx] mod p .
En línea

  El mal es malo también para sí mismo. Por eso, a la larga, sólo puede triunfar el bien. Y por eso también la libertad es buena y deseable..  F. Moreno 
Fernando Moreno
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 260


Ver Perfil
« Respuesta #82 : 22 Diciembre, 2019, 18:51 »

Hola. Los casos que no son  [texx]p\equiv 3[/texx] mod 4 ,  no son completamente generalizables. Si se estudia:  [texx]17![/texx] ;  entonces:  [texx]\dfrac{16}{4}\neq{impar}[/texx] .  En este caso en concreto me da (si no me he equivocado), 7 parejas congruentes con -1 y una, la que queda, con 1. Son:  [texx]16\cdot{1}[/texx]  ,  [texx]8\cdot{2}[/texx]  ,  [texx]5\cdot{10}[/texx]  ,  [texx]11\cdot{13}[/texx]  ,  [texx]9\cdot{15}[/texx]  ,  [texx]6\cdot{14}[/texx]   [texx]\wedge[/texx]   [texx]7\cdot{12}[/texx] .  Y la que queda congruente con 1 es:  [texx]4\cdot{13}[/texx] .  No sé si todo esto sirve para algo, pero es entretenido.
En línea

  El mal es malo también para sí mismo. Por eso, a la larga, sólo puede triunfar el bien. Y por eso también la libertad es buena y deseable..  F. Moreno 
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.037


Ver Perfil
« Respuesta #83 : 22 Diciembre, 2019, 19:03 »

Hola

 No tengo mucho tiempo ahora, pero el camino que propones Fernando, es muy parecido al habitual (que aparece por ejemplo en Gaussianos). Allí lo que se hace es entre los [texx]1,2,3,\ldots,p-1[/texx] emparejar cada número con su inverso módulo [texx]p[/texx], es decir, emparejar números que verifican [texx]xy=1[/texx] mod [texx]p[/texx]. Tu ahí lo complicas ligeramente analizando los que verifican [texx]xy=-1[/texx], que no es más que emparejar cada número con el opuesto de su inverso; dependiendo de si [texx]p=3[/texx] mod [texx]4[/texx] aparecen o no dos elemento [texx]x[/texx] tal que [texx]x^2=-1[/texx] mod [texx]p.[/texx]

Saludos.
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 926



Ver Perfil
« Respuesta #84 : 23 Diciembre, 2019, 08:24 »

Muy bien, Fernando. Ese camino sí que lleva a una denostración correcta del teorema de Wilson. Aunque esencialmente ya lo ha dicho todo Luis: es una demostración parecida a la usual pero más enredada, porque debes distinguir casos según si [texx]-1[/texx] es un cuadrado módulo [texx]p[/texx] o no.

Sobre lo que pones en tu mensaje solamente una cosa: en el caso [texx]p \equiv 1 \mod 4[/texx], que es el caso en que [texx]-1[/texx] es un cuadrado módulo [texx]p[/texx], aparecen [texx]\frac{p-3}{2}[/texx] parejas que al multiplicar dan [texx]-1[/texx], y no [texx]\frac{p-1}{4}[/texx] como dices tú. El motivo es que dado un [texx]x \neq 0[/texx] siempre existe un [texx]y[/texx] único módulo [texx]p[/texx] tal que [texx]xy \equiv -1 \mod p[/texx]  (porque todos los elementos no nulos son invertibles módulo [texx]p[/texx] si [texx]p[/texx] es primo) y tenemos que [texx]y \neq x[/texx] (luego forman una pareja) a no ser que [texx]x^2 \equiv -1 \mod p[/texx]. Pero si [texx]p \equiv 1 \mod 4[/texx] hay exactamente dos [texx]x[/texx] tales que [texx]x^2 \equiv -1 \mod p[/texx], y además su producto es [texx]1[/texx].
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
Fernando Moreno
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 260


Ver Perfil
« Respuesta #85 : 23 Diciembre, 2019, 10:27 »

Hola. Muchas gracias Luis y geómetracat por las explicaciones. Me ha quedado claro.

Sobre lo que pones en tu mensaje solamente una cosa: en el caso [texx]p \equiv 1 \mod 4[/texx], que es el caso en que [texx]-1[/texx] es un cuadrado módulo [texx]p[/texx], aparecen [texx]\frac{p-3}{2}[/texx] parejas que al multiplicar dan [texx]-1[/texx], y no [texx]\frac{p-1}{4}[/texx] como dices tú. El motivo es que dado un [texx]x \neq 0[/texx] siempre existe un [texx]y[/texx] único módulo [texx]p[/texx] tal que [texx]xy \equiv -1 \mod p[/texx]  (porque todos los elementos no nulos son invertibles módulo [texx]p[/texx] si [texx]p[/texx] es primo) y tenemos que [texx]y \neq x[/texx] (luego forman una pareja) a no ser que [texx]x^2 \equiv -1 \mod p[/texx]. Pero si [texx]p \equiv 1 \mod 4[/texx] hay exactamente dos [texx]x[/texx] tales que [texx]x^2 \equiv -1 \mod p[/texx], y además su producto es [texx]1[/texx].

En lo señalado en rojo tenía especialmente una laguna teórica. Pensaba que 2 elementos eran invertibles en la multiplicación si daban 1, no: -1 . Debo entender entonces que a -1 se le considera también una unidad en el Cuerpo que deben formar este Grupo de números no?

Un saludo,
En línea

  El mal es malo también para sí mismo. Por eso, a la larga, sólo puede triunfar el bien. Y por eso también la libertad es buena y deseable..  F. Moreno 
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 926



Ver Perfil
« Respuesta #86 : 23 Diciembre, 2019, 10:37 »

No, no, lo tienes bien entendido: [texx]x[/texx] es invertible si existe un [texx]y[/texx] tal que [texx]xy=yx=1[/texx]. Eso sí: ser invertible es una propiedad de un elemento, no de dos. Si quieres hacer referencia al par puedes decir que ambos elementos son inversos, o que [texx]y[/texx] es el inverso de [texx]x[/texx].

Lo que pasa es que si [texx]x[/texx] es invertible, y [texx]a[/texx] es un elemento cualquiera (en particular esto se aplica a [texx]a=-1[/texx]), existe un único [texx]y[/texx] tal que [texx]xy=a[/texx]. En efecto, basta tomar [texx]y=x^{-1}a[/texx]. Esto es lo que usaba en la frase que has remarcado.

Aunque por otro lado, también es cierto que [texx]-1[/texx] es una unidad en cualquier cuerpo. En general, se define unidad de un anillo como un elemento que es invertible. Como [texx](-1)(-1)=1[/texx], él es su propio inverso, así que [texx]-1[/texx] es invertible.

Es una notación un poco confusa, pero hay que distinguir "ser una unidad" de un anillo (= ser invertible) con la unidad del anillo (que es el [texx]1[/texx]).
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.768



Ver Perfil
« Respuesta #87 : 24 Diciembre, 2019, 07:07 »


Hola, Fernando.

Hola. Quizás exista una manera alternativa de demostrar el Teorema de Wilson. Os lo propongo como tarea (y esta no se puede buscar por internet -que yo sepa). Yo lo voy a intentar también, pero conozco mis limitaciones. Supongo que hay que utilizar Teoría de Grupos.

Haciendo números me doy cuenta de lo siguiente:

Para todo primo impar  [texx]p[/texx] :

1.  [texx](p-1)^{(impar)}\equiv\,p-1[/texx] mod p .

2.  [texx](p-1)^{(par)}\equiv\,1[/texx] mod p .

No sé cuál es la explicación.


Toda la cuestión de esto radica en que tenemos un número “n” (o “p”) y su anterior y su siguiente, n-1 y n+1.

Lo que se puede usar (que al final va a ser lo mismo que dice en Gaussianos) es que dados tres números consecutivos cualesquiera, éstos pueden tener, como mucho, un factor primo en común, el 2. No pueden ser dos de ellos múltiplos de ningún primo más grande. Para asegurarlo basta contar con la idea que nos da el principio de Dirichlet (el del palomar, que te da la explicación más "visualizable") o simplemente pensar en los restos posibles; es una cuestión de distancias: para que haya dos múltiplos de 3, entre ellos tiene que haber dos números; para que haya dos de cinco, en medio de los dos tiene que haber cuatro...

Así, si “n” es par, al lado tiene dos impares y es coprimo con ellos; si es impar, al lado tiene dos pares y pasa lo mismo.

Por tanto, al considerar n-1, n, n+1, resulta que “n” nunca tiene un factor primo en común con los que están a su lado. A partir de ahí, y considerando que un número nunca divide a otro más pequeño, asumir la verdad del teorema es casi trivial.

Feliz Nochebuena.
En línea

Fernando Moreno
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 260


Ver Perfil
« Respuesta #88 : 24 Diciembre, 2019, 14:49 »

Hola feriva,

Toda la cuestión de esto radica en que tenemos un número “n” (o “p”) y su anterior y su siguiente, n-1 y n+1.

Lo que se puede usar (que al final va a ser lo mismo que dice en Gaussianos) es que dados tres números consecutivos cualesquiera, éstos pueden tener, como mucho, un factor primo en común, el 2. No pueden ser dos de ellos múltiplos de ningún primo más grande. Para asegurarlo basta contar con la idea que nos da el principio de Dirichlet (el del palomar, que te da la explicación más "visualizable") o simplemente pensar en los restos posibles; es una cuestión de distancias: para que haya dos múltiplos de 3, entre ellos tiene que haber dos números; para que haya dos de cinco, en medio de los dos tiene que haber cuatro...

Así, si “n” es par, al lado tiene dos impares y es coprimo con ellos; si es impar, al lado tiene dos pares y pasa lo mismo.

Por tanto, al considerar n-1, n, n+1, resulta que “n” nunca tiene un factor primo en común con los que están a su lado. A partir de ahí, y considerando que un número nunca divide a otro más pequeño, asumir la verdad del teorema es casi trivial.

Feliz Nochebuena.

No entiendo lo que dices. Pareces intentar resolver el problema por divisibilidad, sin acudir a congruencias. Tampoco creo que sea un problema tan trivial, como dices. Cuando tengas tiempo si quieres muéstrame tu método por ejemplo con el primo: 11; para  [texx]10¡[/texx] .  Me voy ya para la cena. Feliz Nochebuena
En línea

  El mal es malo también para sí mismo. Por eso, a la larga, sólo puede triunfar el bien. Y por eso también la libertad es buena y deseable..  F. Moreno 
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.768



Ver Perfil
« Respuesta #89 : 24 Diciembre, 2019, 14:52 »

Hola feriva,

Toda la cuestión de esto radica en que tenemos un número “n” (o “p”) y su anterior y su siguiente, n-1 y n+1.

Lo que se puede usar (que al final va a ser lo mismo que dice en Gaussianos) es que dados tres números consecutivos cualesquiera, éstos pueden tener, como mucho, un factor primo en común, el 2. No pueden ser dos de ellos múltiplos de ningún primo más grande. Para asegurarlo basta contar con la idea que nos da el principio de Dirichlet (el del palomar, que te da la explicación más "visualizable") o simplemente pensar en los restos posibles; es una cuestión de distancias: para que haya dos múltiplos de 3, entre ellos tiene que haber dos números; para que haya dos de cinco, en medio de los dos tiene que haber cuatro...

Así, si “n” es par, al lado tiene dos impares y es coprimo con ellos; si es impar, al lado tiene dos pares y pasa lo mismo.

Por tanto, al considerar n-1, n, n+1, resulta que “n” nunca tiene un factor primo en común con los que están a su lado. A partir de ahí, y considerando que un número nunca divide a otro más pequeño, asumir la verdad del teorema es casi trivial.

Feliz Nochebuena.

No entiendo lo que dices. Pareces intentar resolver el problema por divisibilidad, sin acudir a congruencias. Tampoco creo que sea un problema tan trivial, como dices. Cuando tengas tiempo si quieres muéstrame tu método por ejemplo con el primo: 11; para  [texx]10¡[/texx] .  Me voy ya para la cena. Feliz Nochebuena

No todo es congruencias en la vida :sonrisa:

https://es.wikipedia.org/wiki/Principio_del_palomar

Viene a ser muy parecido divisibilidad, congruencias, modularidad... pero dependiendo de qué problemas se ven las cosas mejor de una manera u otra.

Si dos números, “a,b” están a una distancia “d”, su mcd, como mucho, es “d”. Si tuvieran un factor común mayor que “d”, querría decir que son dos representantes distintos de ese número, de ese factor; y que, por tanto, su distancia sería un múltiplo también de dicho entero. Con eso se puede justificar y visualizar perfectamente que dos números consecutivos son coprimos; por ser su distancia 1. Y dicho así no cabe hablar de congruencias, porque no estamos considerando ningún módulo en concreto; no hace falta, esto es general independiéntemente de la multiplicidad de “a,b”; y también de que uno de ellos esté a la izquierda y otro a la derecha (lo mismo pasa si es n+1 que n-1; no hay que dar vueltas al signo).

Ahora, si escribimos el factorial así [texx](n-1)!=k(n-1)
 [/texx]

y consideramos que un factor de “n” divide a

[texx]k(n-1)
 [/texx]

ya hemos justificado que no divide a “n-1”, luego tendría que dividir a “k”.

Si segudiamente consideramos que divide a

[texx]k(n-1)+1=
 [/texx]

[texx]kn-k+1=
 [/texx]

[texx]kn-(k-1)
 [/texx]

resulta que también tiene que dividir al (k-1); donde “k”, análogamente a lo que ocurría con “n”, es el siguiente de éste, luego es imposible.


Feliz Navidad

En línea

Páginas: 1 ... 3 4 [5]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!