Autor Tema: Variante de demostración del Teorema de Wilson

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

25 Diciembre, 2019, 07:12 pm
Leído 3213 veces

Fernando Moreno

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 284
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola,


El Teorema:  \( \pmb{(p-1)¡\equiv\,p-1} \) mod p.

1. Sólo funciona para Módulo números primos. Haciendo números es inmediato lo siguiente:  Dado un  \( p \)  \( \Rightarrow \)  \( \pmb{p-1\mid 2(p-3)¡} \) .  Luego  \( (p-2)¡\equiv\,0,2 \) mod \( (p-1) \)  -y- no puede ser entonces  \( (p-2)¡ \)  congruente con  \( p-2 \)  Módulo  \( p-1 \)  y esto vale para cualquier número compuesto.

2. La demostración. Es una tautología que:  \( \left({\dfrac{p-n+1}{n}+1}\right)\cdot n\equiv\,1 \) mod p .  Luego tendremos:

 \( \pmb{(p+1)\cdot 1\equiv\,1} \) mod p

\( \pmb{\left({\dfrac{p-1}{2}+1}\right)\cdot 2\equiv\,1} \)  mod p

\( \pmb{\left({\dfrac{p-2}{3}+1}\right)\cdot 3\equiv\,1} \)  mod p

.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .

\( \left({\dfrac{p-(p-1)+1}{p-1}+1}\right)\cdot p-1\equiv\,1 \) mod p  \( \Rightarrow \)  \( \left({\dfrac{1}{\dfrac{p-1}{2}}+1}\right)\cdot p-1\equiv\,1 \) mod p .  Como el inverso de  \( \dfrac{p-1}{2} \)  es  \( p-2 \) ;  puesto que:  \( \dfrac{p-1}{2}\cdot p-2\equiv\,\dfrac{-1}{2}\cdot (-2)\equiv\,1 \)  mod p .  Entonces:

\( \pmb{(p-2\,+1)\,\cdot\,p-1\equiv\,1} \)  mod p .


Luego las únicas parejas multiplicativas solteras dentro de  \( (p-1)¡ \)  son:  \( 1 \)  \( \wedge \)  \( p-1 \) .  Luego:  \( (p-1)¡\equiv\,p-1 \) mod p .


Bueno. Ahora contemos la verdad  ;) . Yo en realidad lo que he estado buscando es una demostración por el absurdo de si  \( (p-1)¡ \)  era congruente con otra cosa que no fuera:  \( p-1 \) .  Pero no lo he conseguido. Es decir, en principio no hay ninguna contradicción en que  \( (p-1)¡ \)  fuera congruente con  \( p-2 \)  ,  \( p-3 \)  ,  etc.  (ó yo no la he encontrado)


Un saludo y Feliz Navidad


PD.  ya puedo seguir entonces con el "rollo" del UTF de nuevo    :-[
An expert is a man who has made all the mistakes, which can be made, in a very narrow field. Niels Bohr

25 Diciembre, 2019, 10:31 pm
Respuesta #1

Juan Pablo Sancho

  • Moderador Global
  • Mensajes: 5,006
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sea \( a \in \{0,1,2, \cdots ,n-1\} = A  \) tenemos que \( mcd(a,p)=1 \) entonces para todo \( a \in A  \)
la ecuación \( ax \equiv 1  \) mod(p) tiene solución única.
En que caso \(  x = a  \) en el que verifica \(  a^2 \equiv 1  \) mód(p) que es lo mismo que:
\( a^2 - 1 \equiv 0  \) mód(p)  como \( a^2-1 = (a-1) \cdot (a+1)  \) tendremos que:
\( (a-1) \equiv 0  \) mód(p) y esto sólo sucede para \( a=1 \)
o  \( (a+1) \equiv 0  \) mód(p) y esto sólo sucede para \( a = p-1 \equiv -1  \)

Editado
Pero si \( p=7 \) por ejemplo tienes que:
\( (\dfrac{p-2}{3}+1) = \dfrac{8}{3} \notin \mathbb{Z}  \)
Editado 2
Veo que no tiene nada que ver con lo que expones.
Error del menda.


25 Diciembre, 2019, 11:22 pm
Respuesta #2

Fernando Moreno

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 284
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Sea \( a \in \{0,1,2, \cdots ,n-1\} = A  \) tenemos que \( mcd(a,p)=1 \) entonces para todo \( a \in A  \)
la ecuación \( ax \equiv 1  \) mod(p) tiene solución única.
En que caso \(  x = a  \) en el que verifica \(  a^2 \equiv 1  \) mód(p) que es lo mismo que:
\( a^2 - 1 \equiv 0  \) mód(p)  como \( a^2-1 = (a-1) \cdot (a+1)  \) tendremos que:
\( (a-1) \equiv 0  \) mód(p) y esto sólo sucede para \( a=1 \)
o  \( (a+1) \equiv 0  \) mód(p) y esto sólo sucede para \( a = p-1 \equiv -1  \)

Editado
Pero si \( p=7 \) por ejemplo tienes que:
\( (\dfrac{p-2}{3}+1) = \dfrac{8}{3} \notin \mathbb{Z}  \)

Si p=7. Entonces:  \( (\dfrac{p-2}{3}+1) = \dfrac{5}{3}+1=5\cdot\dfrac{1}{3}+1\equiv\,5\cdot 5 +1\equiv\,26\equiv\,5 \) mod 7. Puesto que el inverso de 3 Módulo 7 es 5. Creí que conocías que este Grupo de números es un cuerpo y admite la división. La variante de demostración que pongo permite precisamente saber exactamente con qué número Módulo un primo cualquiera tiene el inverso uno de sus restos. 

Añado: Lo dicho último sobre todo es válido en los casos en que la división es posible. En los que no, como el del ejemplo, me veo obligado a buscar el inverso "a pelo" antes de llegar a la conclusión. En todo caso esta demostración no pretende ser otra cosa que "una variante", nada más, ni mejor ni peor
An expert is a man who has made all the mistakes, which can be made, in a very narrow field. Niels Bohr

26 Diciembre, 2019, 10:11 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,875
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

  Fernando Moreno. No acabo de entender exactamente dónde está la variación en lo que has escrito.

 Como te ha indicado Juan Pablo Sánchez, en todos los casos en los que \( p+1 \) no es divisible por \( k \), el cociente \( \dfrac{p-k+1}{k} \) no es entero. Entonces efectivamente tiene sentido considerarlo usando que \( k \) es inversible módulo \( p \). Pero para ese viaje no hacían falta alforjas. Si lo que vamos a usar es que sabemos que todo número no múltiplo de \( p \) tiene inverso multiplicativo módulo \( p \), el intento por explicitar tal inverso sobra. No aporta nada. No sustituye al resultado previo de saber que tal inverso existe. Y realmente en la mayor parte de los casos la supuestas expresión explícita del inverso es un "engaño"; no es efectiva.

 Por otra parte aún te faltaría justificar, que sólo hay dos elementos que coinciden con su inverso.

Saludos.

26 Diciembre, 2019, 10:16 am
Respuesta #4

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,436
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Hola, Fernando.



Bueno. Ahora contemos la verdad  ;) . Yo en realidad lo que he estado buscando es una demostración por el absurdo

Si quieres hacerlo por el absurdo, la hipótesis contraria implica \( n=ab;\,|a|>1;\,|b|>1
  \), tienes que usar eso, es la definición de compuesto, cualquier otra será lo mismo dicho con otras palabras. Y entonces, de aquí, \( (n-1)!+1\equiv0\,(mod\, ab)
  \), es inmediato que ni “a” ni “b” divide a \( (n-1)!
  \) (se puede explicar por qué si se quiere, pero ya se lo sabe todo el mundo) lo que implica, más trivialmente aún, que tiene que dividir a un número mayor que \( (n-1) \), y el único posible es “n”.

Hay veces que las cosas sólo tienen un demostración que quede natural (que se pueda considerar normal, sin dar vueltas).



Saludos

26 Diciembre, 2019, 11:18 am
Respuesta #5

Fernando Moreno

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 284
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Por otra parte aún te faltaría justificar, que sólo hay dos elementos que coinciden con su inverso.

Entiendo que eso que dices no hace falta. Lo que muestro es que sólo 2 elementos no tienen "pareja" dentro de  \( (p-1)¡ \) .  " \( 1 \) " ,  cuya pareja es:  \( p+1 \)  -y-  " \( p-1 \) "  cuya pareja sí demuestro que es él mismo:  \( p-2+1=p-1 \) .

Si lo que vamos a usar es que sabemos que todo número no múltiplo de \( p \) tiene inverso multiplicativo módulo \( p \), el intento por explicitar tal inverso sobra. No aporta nada. No sustituye al resultado previo de saber que tal inverso existe. Y realmente en la mayor parte de los casos la supuestas expresión explícita del inverso es un "engaño"; no es efectiva.

Por otra parte disculpas si resulta que os he engañado a todos. Por lo menos en la parte que sí se da la división, te da de una manera directa quién es el inverso del resto dentro de  \( (p-1)¡ \) .  Y eso, al menos para mí, resulta curioso y es una pequeña variación.


Bueno. Ahora contemos la verdad  ;) . Yo en realidad lo que he estado buscando es una demostración por el absurdo

Eso está sacado de contexto. La cita completa es la siguiente:

Bueno. Ahora contemos la verdad  ;) . Yo en realidad lo que he estado buscando es una demostración por el absurdo de si  \( (p-1)¡ \)  era congruente con otra cosa que no fuera:  \( p-1 \) .  Pero no lo he conseguido. Es decir, en principio no hay ninguna contradicción en que  \( (p-1)¡ \)  fuera congruente con  \( p-2 \)  ,  \( p-3 \)  ,  etc.  (ó yo no la he encontrado)

Si para ti es inmediato demostrar que si  \( (p-1)¡ \)  es congruente por ejemplo con  \( p-2 \)  implica una contradicción. Dímelo, pero no con intenciones, si no con los números; que no lo entiendo y yo no he sido capaz de sacar la demostración.

Un saludo,
An expert is a man who has made all the mistakes, which can be made, in a very narrow field. Niels Bohr

26 Diciembre, 2019, 12:40 pm
Respuesta #6

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,436
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

Hola, Fernando.


Si para ti es inmediato demostrar que si  \( (p-1)¡ \)  es congruente por ejemplo con  \( p-2 \)  implica una contradicción. Dímelo, pero no con intenciones, si no con los números; que no lo entiendo y yo no he sido capaz de sacar la demostración.

Un saludo,


Pero para qué quieres eso.

Usa que \( (p-1)!=(p-3)!(p-2)(p-1)
  \), que se ve mejor.

\( (p-3)!(p-2)(p-1)\equiv(p-2)\ (mod\,\, lo_{-}que\, sea)
  \)

¿En qué caso deja resto (p-2)?

En principio, o es equivalente a resto cero o sólo podría ser si p-2=1, si no, no tiene sentido; divide la congruencia entre p-2 a los dos lados

\( (p-3)!(p-1)\equiv1\ (mod\,\, lo_{-}que\, sea)
  \)

Es más, aunque no sea ese factorial, puede ser cualquier número multiplicado por (p-2) y pasa lo mismo; por ejemplo:

\( 2\cdot3\cdot5\equiv2\ (mod\,7)
  \)

\( 3\cdot5\equiv1\ (mod\,7)
  \)

Se ve bien, no hacen falta más ejemplos.

Luego es equivalente a considerar

\( (p-2)k\equiv(p-2)\,(mod\, p)
  \)

\( k\equiv1\,(mod\, p)
  \)

Está fuera de lo que considera Wilson, el resto sería 1 o cero, no -1.

Saludos.

26 Diciembre, 2019, 12:48 pm
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,875
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Entiendo que eso que dices no hace falta. Lo que muestro es que sólo 2 elementos no tienen "pareja" dentro de  \( (p-1)¡ \) .  " \( 1 \) " ,  cuya pareja es:  \( p+1 \)  -y-  " \( p-1 \) "  cuya pareja sí demuestro que es él mismo:  \( p-2+1=p-1 \) .

¿Cómo lo muestras? ¿Por qué el inverso módulo \( 17 \) de \( 8 \) no podría ser de nuevo \( 8 \) (evidentemente no lo es)?.¿Dónde está la justifiación?.

Citar
Por otra parte disculpas si resulta que os he engañado a todos. Por lo menos en la parte que sí se da la división, te da de una manera directa quién es el inverso del resto dentro de  \( (p-1)¡ \) .  Y eso, al menos para mí, resulta curioso y es una pequeña variación.

Es más bien un añadido. Porque no evitas que a priori tengas que usar otro resultado que garantice la existencia del  inverso. Añadido que otras demostraciones no se molestan en hacer porque es prescindible.

Si quieres hacerlo por el absurdo, la hipótesis contraria implica \( n=ab;\,|a|>1;\,|b|>1
  \), tienes que usar eso, es la definición de compuesto, cualquier otra será lo mismo dicho con otras palabras. Y entonces, de aquí, \( (n-1)!+1\equiv0\,(mod\, ab)
  \), es inmediato que ni “a” ni “b” divide a \( (n-1)!
  \) (se puede explicar por qué si se quiere, pero ya se lo sabe todo el mundo) lo que implica, más trivialmente aún, que tiene que dividir a un número mayor que \( (n-1) \), y el único posible es “n”.

Hay veces que las cosas sólo tienen un demostración que quede natural (que se pueda considerar normal, sin dar vueltas).

feriva: una y otra vez me parece que estás hablando de la parte fácil de Teorema.

Lo que quieres probar Fernando es que si \( p \) es primo entonces \( (p-1)!=-1 \) mod \( p \). Por reducción al absurdo sería probar que si \( (p-1)!\neq -1 \) mod \( p \) entonces \( p \) no es primo.


Si para ti es inmediato demostrar que si  \( (p-1)¡ \)  es congruente por ejemplo con  \( p-2 \)  implica una contradicción. Dímelo, pero no con intenciones, si no con los números; que no lo entiendo y yo no he sido capaz de sacar la demostración.

Un saludo,

Pero para qué quieres eso.

feriva: no entiendo nada.

Citar
Usa que \( (p-1)!=(p-3)!(p-2)(p-1)
  \), que se ve mejor.

\( (p-3)!(p-2)(p-1)\equiv(p-2)\ (mod\,\, lo_{-}que\, sea)
  \)

¿En qué caso deja resto (p-2)?

En principio, o es equivalente a resto cero o sólo podría ser si p-2=1, si no, no tiene sentido; divide la congruencia entre p-2 a los dos lados

¿Qué es lo que no tiene sentido y por qué?.

Citar
\( (p-3)!(p-1)\equiv1\ (mod\,\, lo_{-}que\, sea)
  \)

Es más, aunque no sea ese factorial, puede ser cualquier número multiplicado por (p-2) y pasa lo mismo; por ejemplo:

\( 2\cdot3\cdot5\equiv2\ (mod\,7)
  \)

\( 3\cdot5\equiv1\ (mod\,7)
  \)

"Pasa lo mismo". ¿Qué es lo mismo?¿A qué te refieres?.

Saludos.

26 Diciembre, 2019, 01:46 pm
Respuesta #8

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,436
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, Luis.


feriva: una y otra vez me parece que estás hablando de la parte fácil de Teorema...




Yo parto de que si “p” es primo, quiere decir que cumple estas condiciones

\( p=ab:\,(|a|=1\wedge|b|\neq1)\vee(|a|\neq1\wedge|b|=1)
  \)

Cuando ni |a| y ni |b| es 1, no cumple eso, es compuesto. A partir de ahí hago la suposición de que no es primo para llegar a que sí lo es.

Si ahora considero,\( (p-1)!\equiv-1\,(mod\, ab)
  \), o lo que es lo mismo, \( (p-1)!+1\equiv0\,(mod\, ab)
  \), al no ser “a” igual a 1ni tampoco “b”, ningún factor divide a \( (p-1)!
  \) (lo que considero inmediato de ver).

Que “a” ó “b” (cualquier factor de p, el que sea) no divida a \( (p-1)!
  \) implica trivialmente, por definición de factorial, que no divida a ningún número natural menor o igual que (p-1). Por tanto, “a” (o el factor “b”, sin perder generalidad) es un número mayor que (p-1). Igualmente me parece obvio que ese factor mayor que (p-1) no puede ser mayor que el propio “p”; ningún número tiene un factor mayor que sí mismo. Luego a=p y b=1, o viceversa, y entonces p es primo.

Ah, ya veo, no estoy demostrando la contraria; es que me lio...

En cuanto a lo otro, me he despistado, sí, tienes razón; y además no sé si he entiendo lo que me preguntaba.

Entiendo que decía que no podía demostrar que \( (p-1)! \) no puede dejar resto (p-2) módulo p. Y lo que yo le decía era que considerara el factorial escrito así \( (p-1)!=(p-3)!(p-2)(p-1)
  \) para, después, analizarlo para cualquier módulo, dejando resto (p-2). Y esto, veo ahora, que no tiene nada que ver, porque él se refería a módulo p.

Sería entonces (creo) equivalente a considerar esto

\( (p-3)!(p-2)(p-1)\equiv(p-2)\,(mod\, p)
  \).

\( (p-3)!(p-1)\equiv1\,(mod\, p)
  \)

¿Estoy entendiéndolo ahora?

Muchas gracias, Luis; y Feliz Navidad.

26 Diciembre, 2019, 03:37 pm
Respuesta #9

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,436
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, Fernando.

El otro día, en mi post, entendí otra cosa al decirme Luis lo de la demostración en el sentido fácil; interpretaba que había que demostrar primero que no era compuesto; y, después, con la Nocehbuena y todo eso, pues ya no releí, me he dado cuenta cuando me lo ha dicho ahora otra vez.


Esto no sirve para nada, ya pondré otra cosa

Spoiler
Entonces, ya sí entiendo; vamos a ver lo que pasa; suponemos por comodidad enteros positivos:
\( (p-1)!\equiv-r(mod_{\,}p)
  \); donde “p” primo y \( r>1
   \) (mayor que 1 como clase de equivalencia, para atacarlo por reducción al absurdo).

Tenemos también que, como \( p>p-1
  \), entonces \( r\leq(p-1)
  \), por lo que

\( r\in[1,(p-1)]
  \)

lo que nos permite escribir

\( (p-1)!\equiv kr
  \); con k>1.

Y, por tanto, igualmente podemos escribir

\( kr\equiv-r\,(mod_{\,}p)
  \)

\( kr+r\equiv0\,(mod_{\,}p)
  \)

Factorizando

\( r(k+1)\equiv0\,(mod_{\,}p)
  \)

Donde p, por ser mayor, no puede divdir a “r”, luego divide a k+1.

Pero si divide a k+1, entonces, como es primo, \( k+1=mp \) y \( k=mp-1 \), con “m” coprimo con “p”-

De aquí \( kr\equiv-r\,(mod_{\,}p)
  \), sutituyendo k por (p-1)

\( (mp-1)r\equiv-r\,(mod_{\,}p)
  \)

Donde sólo si r es equivalente a 1 se cumple la congruencia:

\( mp-1\equiv-1\,(mod_{\,}p)
  \).

A ver si está bien ahora.
[cerrar]

                                                                            NUEVO

 
Spoiler
                            ...
[/color]

Si \( (p-1)!\equiv-r(mod_{\,}p)
  \), por el algoritmo de Euclides tendremos

\( mcd[(p-1)!,\; p]=mcd[p,r]=1
  \) (pues r es distinto de p)

Y tenemos

\( mcd(p,r)\cdot mcm(p,r)=pr
  \)

\( mcd(p,r)=\dfrac{p\cdot r}{mcm(pr)}
  \)

El mínimo común múltiplo de p y r es un entero múltiplo de “p” y de “r” necesariamente... Y...


[cerrar]



Me he desesperado,  como la niña ésta  https://www.trendsmap.com/twitter/tweet/1209317301113241600



Saludos.