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

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

27 Diciembre, 2019, 08:48 am
Respuesta #20

Fernando Moreno

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


Si tomas 11, por ejemplo

1,2,3,4,5,6,7,8,9,10,(11)

son éstas

\( 2\cdot6\equiv1(11)
  \)

\( 3\cdot4\equiv1(11)
  \)

\( 5\cdot9\equiv1(11)
  \)

\( 7\cdot8\equiv1(11)
  \)

No hay un orden, para cada primo las parejas se forman de distinta manera; parece un intrincado problema de combinatoria.

Utiliza esta fórmula:  \( \displaystyle\frac{p+1}{k}=\,Inverso\,de\,\color{red}k \) mod p .

\( \displaystyle\frac{12}{\color{red}2}=6 \)  ,  \( \displaystyle\frac{12}{\color{red}3}=4 \)  ,  \( \displaystyle\frac{12}{\color{red}5}=\dfrac{24}{10}\equiv 24\cdot 10=240\equiv 9 \)   \( \wedge \)   \( \displaystyle\frac{12}{\color{red}7}=\displaystyle\frac{24}{14}\equiv{\dfrac{24}{3}}=8 \) .

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

27 Diciembre, 2019, 10:26 am
Respuesta #21

feriva

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


Utiliza esta fórmula:  \( \displaystyle\frac{p+1}{k}=\,Inverso\,de\,\color{red}k \) mod p .

\( \displaystyle\frac{12}{\color{red}2}=6 \)  ,  \( \displaystyle\frac{12}{\color{red}3}=4 \)  ,  \( \displaystyle\frac{12}{\color{red}5}=\dfrac{24}{10}\equiv 24\cdot 10=240\equiv 9 \)   \( \wedge \)   \( \displaystyle\frac{12}{\color{red}7}=\displaystyle\frac{24}{14}\equiv{\dfrac{24}{3}}=8 \) .

Saludos, 

Buenos días, Fernando.

Sí, se pueden calcular, pero si yo tomo el 2, por ejemplo, y busco sus inversos respectivos para \( Z_{5},Z_{7},Z_{11}...
  \) obtengo esta secuencia (si no me equivoco en alguno)

3,4,6,7,8,9,10,12,15,16,19,...

y la sucesión no tiene un término \( a_{n}
  \) general (no es que yo no lo sepa encontrar, Wolframalpha no lo da).

Siempre podremos, supongo (aunque no he probado) encontrar una fórmula interpolando por Taylor, o Newton o quien sea, que funcione hasta cierto sitio, pero no funcionará en general, hasta el “final”.

Saludos.

27 Diciembre, 2019, 10:38 am
Respuesta #22

Luis Fuentes

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

Realmente para que se dé una situación de  \( n\cdot{n} \)  si  \( (\displaystyle\frac{p+1}{n})\cdot n \)   \( \Rightarrow{} \)   \( p+1 \)  debe ser igual á  \( n^2 \) .  Pero entonces, salvo que  \( n=2 \) ;  \( n^2-1\neq{p} \)  porque  \( (n+1)(n-1)\neq{p} \) .  Luego sigo, ahora no puedo. A ver si puedo resumirlo todo mejor.

¡Así, si!. Eso es lo que demuestra que los únicos números que coinciden con su inverso multiplicativo módulo \( p \) son \( 1 \) y \( -1\equiv p-1 \). Se usa de manera decisiva que \( p \) es primo.

En cuanto a mi crítica a tu "variación" de la demostración, el resumen es:

- Usas (la das por conocida; tu no la demuestras) de manera ineludible la propiedad de que módulo \( p \) primo todo número no equivalente al cero tiene inverso multiplicativo.
- Para algunos casos das una expresión explícita del inverso. Pero eso es accesorio, innecesario para que tu demostración funcione. No se necesita esa expresión explícita para terminar la prueba. Y por otro lado como he dicho antes, como esa expresión no funciona siempre, no elude el uso de la propiedad de existencia de inverso.
- Adicionalmente, pero eso es otro tema está la discusión de cuan interesante o novedosa es esa expresión previa.

Al margen de lo anterior. La fórmula también me sirve para atajar el cómo averiguar cuál es el inverso de, por ejemplo, el que pones: 8 Módulo 17. Tendremos que su inverso será:  \( \dfrac{p-7}{8}+1=\dfrac{10}{8}+1=1+0,25+1=2+\dfrac{1}{2}\cdot\dfrac{1}{2} \) .  Como el inverso de 2 Módulo 17 es inmediato que es 9; tendré:  \( 2+81=83\equiv\,15 \) mod 17. Ésta es la respuesta: 15.

Pero es que con el método usual ese inverso se calcula igual de rápidamente. Básicamente se trate de resolver:

\( 8x+17k=1 \)

aplicando el algoritmo extendido  de Euclides. En el primer paso queda:

\( 17=2\cdot 8+1 \) es decir \( (-2)\cdot 8+1\cdot 17=1 \)

y por tanto el inverso es \( x=-2=15 \) mod \( 17 \).

No obstante, el algoritmo extendido de Euclides NO es el método más rápido para calcular inversos multiplicativos en artimétrica modular.

Aquí se comentan otros métodos:

https://es.wikipedia.org/wiki/Inverso_multiplicativo_(aritm%C3%A9tica_modular)

Citar
Esto parece engorroso ahora, pero imaginemos hallar el inverso de 201 Módulo 9883.

¿Cómo lo calculas?.

Spoiler
Con el algoritmo de Euclides es:

\( 9883=49\cdot 201+34 \)
\( 201=5\cdot 34+31 \)
\( 34=31+3 \)
\( 31=10\cdot 3+1\quad \Rightarrow{}\quad 31-10\cdot 3=1 \)

y ahora vamos hacia "atrás":

\( 31-10(34-31)=1\quad \Rightarrow{}\quad 11\cdot 31-10\cdot 34=1 \)
\( 11\cdot (201-5\cdot 34)-10\cdot 34=1\quad \Rightarrow{}\quad 11\cdot 201-65\cdot 34=1 \)
\( 11\cdot 201-65\cdot (9883-49\cdot 201)=1\quad \Rightarrow{}\quad 3196\cdot 201-65\cdot 9883=1 \)

Por tanto el inverso es \( 3196 \).
[cerrar]

Sin utilizar la propiedad de inversos que tienen los números módulo un número primo. O sea, la propiedad de que se pueden dividir exactamente, no lo vas a conseguir nunca. Me apuesto una super-disculpa por escrito en negrita y de color rosa.

Aquí tienes, por ejemplo, una demostración geométrica del Teorema de Wilson:

https://www.cut-the-knot.org/blue/GeometricWilson.shtml

Aquí un enfoque combinatorio:

http://campus.lakeforest.edu/trevino/WilsonCapsule.pdf

Saludos.

P.D. feriva: me cuesta seguir tus mensajes, con corrección sobre corrección y "tirándote abajo" tu mismo tus propias propuestas. ¿Por qué no las trabajas un poco más antes de hacerlas públicas?. No hay prisa.

27 Diciembre, 2019, 11:08 am
Respuesta #23

feriva

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

P.D. feriva: me cuesta seguir tus mensajes, con corrección sobre corrección y "tirándote abajo" tu mismo tus propias propuestas. ¿Por qué no las trabajas un poco más antes de hacerlas públicas?. No hay prisa.

Tienes razón, Luis, perdóname (y perdonadme todos los que me hayáis sufrido por lo de anoche).

Me daba la falsa sensación de que tenía que poderse hacer sin tanta dificultad (dejando aparte la demostración existente) y me enrabietaba cada vez que publicaba y veía que algo estaba mal o se me había olvidado considerar algo.

Intentaré entonces con calma, ya que no puedo de otra manera, demostrar que el inverso existe para los elementos de los Zp y es único (prometo que no conozco la demostración, nunca la he estudiado y no la he buscado en internet, o si la he visto, no me acuerdo); si no puedo en unos días, entonces buscaré.

Muchas gracias, saludos.

28 Diciembre, 2019, 12:02 am
Respuesta #24

feriva

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

\( ax\equiv1\,(mod\, y)
  \); donde \( x,y
  \) son coprimos; o sea \( mcd(x,y)=1
  \).

Lo que lleva a la ecuación diofántica:

\( ax-1=by
  \)

\( ax+by=1
  \) (el signo no importa, se puede poner + porque b puede tomar el signo que convenga).

Se demuestra que siempre existen a,b enteros para los x,y coprimos de esa ecuación; aunque, en realidad, se demuestra más en general que \( ax+by=mcd(x,y)
  \) (no sólo para coprimos); la identidad de Bézout.

Spoiler

Esta famosa demostración la conocía y la he recordado; me ha parecido oportuna para intentar demostrar la existencia de los inversos traídos a colación.

Tenemos como hipótesis \( ax+by=mcd(x,y)
  \).

Existe el conjunto de los números positivos de la forma \( ax+by
  \); conjunto que tendrá algún elemento de valor mínimo, sea “m” (mayor que cero, pues consideramos un conjunto de divisores).

Sea el mínimo entonces: \( m=a_{0}x+b_{0}y
  \).

Esto es claro que existe siempre, pues dados unos x,y cualesquiera, existirán enteros “a,b” (positivos, negativos los dos o uno u otro) de tal forma que la suma sea el valor positivo más pequeño que puede dar dicha adición; lo que no sabemos aún es si existen “a,b” tales que “m” sea el mcd de (x,y).

Entonces, si “m” divide a “x” y también a “y”, por ser el mínimo, será el máximo común divisor de los dos.

Usando el algoritmo de la división podemos escribir

\( x=qm+r
  \)

(esto siempre con m>r, porque, si es al revés, con r=m+k (k positivo)

\( x=qm+m+k=m(q+1)+k
  \) y el resto sería k; y (q+1) haría de q pudiendo reescribir la ecuación con la misma forma retomando las letras).

Y sustituyendo “m” en \( x=qm+r
  \) por \( ax+b_{0}y
  \)

\( x=q(a_{0}x+b_{0}y)+r
  \)

Ahora, despejando y sacando factor común x

\( x(1-qa_{0})-qb_{0}y=r
  \)

Lo que significa que “r” tiene la misma forma y debería pertenecer al conjunto de los divisores; sin embargo, “m”, por hipótesis, es el más pequeño del conjunto y no puede haber otro número de la misma forma que sea menor (pero r<m, como se ha visto).

Entonces, si “m” valiera, por ejemplo, 2 ó 3... en ese caso “r” no podría ser 1 ó 2... porque entonces, al ser el mínimo, “m” también tendría que ser 1 ó 2... y no 2 ó 3... y sería contradictorio; tendríamos algo así \( x=qr+r
  \) y el resto dividiría a “x, que es absurdo. Lo único que puede pasar es que r=0, lo que implica que “m” divide a x.

Exactamente de la misma manera se demuestra que “m” divide a “y; con lo que tienen que existir “a” y “b” tales que pase lo dicho.

[cerrar]

Luego si x,y coprimos, existen a,b tales que \( ax\equiv1\,(mod\, y)
  \), que implica \( ax+by=1
  \), donde “a” es el inverso de “x” módulo “y”.

Para que ocurra esto, “y” no tiene que ser necesariamente primo; y existe el inverso de x siempre.

Ahora bien, si consideramos la congruencia \( (p-2)!\equiv1(mod\, p)
  \), sólo se podrá cumplir si p es primo, de lo contrario, en el factorial habrá un factor común con p.

Por lo dicho, podríamos considerar, por ejemplo, la ecuación diofántica siguiente

\( a(p-2)!+bp=1
  \)

y, por la identidad de Bézout, existe siempre el inverso “a”.

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

También podemos considerar los factores aisladamente

\( a_{2}(p-2)+b_{2}p=1
  \)

\( a_{3}(p-3)+b_{3}p=1
  \)

etc.

....

Supongamos que dos (p-i) pudieran compartir un mismo inverso “a”:

\( a(p-i)+b_{2}p=1
  \)

\( a(p-j)+b_{3}p=1\Rightarrow
  \)

...

\( ap-ai+b_{2}p=1
  \)

\( ap-aj+b_{3}p=1
  \)

Tendríamos dos expresiones de esta forma

\( np-ai-1=0
  \)

\( mp-aj-1=0
  \)

donde i,j son elementos distintos de Zp multiplicados por un mismo número “a”. Sin embargo, junto al -1 que les acompaña, serían equivalentes al mismo resto módulo p.

Creo que esto no puede ser, creo que no pueden dar el mismo resto: \( i\,\not\equiv\, j\Rightarrow  \) \( ai\,\not\equiv\, aj  \)

Y de aquí podríamos afirmar que para cada (p-i) existe un inverso diferente.

¿Sería cierto esto?

Saludos.

28 Diciembre, 2019, 10:13 am
Respuesta #25

Luis Fuentes

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

Luego si x,y coprimos, existen a,b tales que \( ax\equiv1\,(mod\, y)
  \), que implica \( ax+by=1
  \), donde “a” es el inverso de “x” módulo “y”.

Para que ocurra esto, “y” no tiene que ser necesariamente primo; y existe el inverso de x siempre.

Siempre que \( x \) e \( y \) sean coprimos; lo has dicho antes, pero esa frase a modo de conclusión que pones al final podría llevar a confusión.

Cuando \( y \) es primo, \( x \) e \( y \) siempre son coprimos (salvo que \( x \) esté en la clase del cero) y eso es lo que hace que para \( y \) primo todo elemento no nulo tenga inverso.

Citar
Y de aquí podríamos afirmar que para cada (p-i) existe un inverso diferente.

Que elementos inversibles distintos tienen inversos distintos es inmediato y válido en cualquier anillo conmutativo. No hace falta montar semejante galimatías. Simplemente:

\( a^{-1}=b^{-1}\quad \Rightarrow{}\quad (a^{-1})^{-1}=(b^{-1})^{-1}\quad \Rightarrow{}\quad a=b \)

Tu montas un lío innecesario para al final usar que \( i\neq j\quad \Rightarrow{}\quad ai\neq aj \) lo cual es cierto si trabajas en un cuerpo  (en un dominio de hecho) o simplemente si \( a \) es inversible; pero tan sencillo es probar eso como directamente que cada elemento tienen un inverso diferente.

Por otra parte con eso todavía no has probado nada troncal respecto a la parte del Teorema de Wilson que tratas de demostrar.

Saludos.

28 Diciembre, 2019, 10:41 am
Respuesta #26

feriva

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

Por otra parte con eso todavía no has probado nada troncal respecto a la parte del Teorema de Wilson que tratas de demostrar.

Saludos.

Muchísimas gracias, Luis.

Ahora habría que probar, supongo, que existen todos los inversos del tamaño adecuado, es decir, que cada (p-i) tiene un inverso que pertenece a [2, p-2]. ¿Sería este el punto que falta? (prescindo de 1 y de (p-1) que ya sé que su producto es el resto -1 y el cual usaría para multiplicarlo al final).

Anoche estuve pensando un poco precisamente en demostrar esto, pero no sé muy bien cómo hacerlo todavía para que quede del todo riguroso (y también estuve tentado de preguntarte directamente, pero voy a esperar a ver qué se me ocurre).

Sé que es un cuerpo, y algo tengo visto de otra veces (muy, muy por encima) sobre ideales, dominios de integridad... y esas cosas, pero ni idea de cómo se justifica con la corrección necesaria. Lo que sé seguro es que tiene infinitas soluciones, sin embargo, las soluciones en Zp son finitas y hay que ver si están todas para las parejas. Intuitivamente sí me parece claro, pero no sé cómo decirlo (seguro que, de conseguirlo, me dirás también que he dado muchas vueltas; cosa que comprendo que me digas, porque tienes razón; pero es que voy a ciegas, sin conocer casi la teoría).

*Fernando, qué te parece si intentas terminarlo tú (si te apetece); yo lo dejo aquí, lo terminas, y así lo demostramos a medias :)

Saludos.

28 Diciembre, 2019, 02:35 pm
Respuesta #27

Fernando Moreno

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


Esto parece engorroso ahora, pero imaginemos hallar el inverso de 201 Módulo 9883.

¿Cómo lo calculas?.


Ahí va mi método. Reconozco que me ha costado bastante, al haber buscado todas las variantes que he podido para simplificar lo más posible. La que pongo ahora es la mejor.

Parto de Módulo 9883 y busco el inverso de 201. Luego:  \( \displaystyle\frac{9884}{201} \) .  201 cabe en 9884: 49 veces y pico, luego multiplico por 50 en numerador y denominador. A esta operación la voy a llamar (1). Tendré:  \( \displaystyle\frac{494.200}{10.050} \) . " 10.050 " es congruente 167 con 9883. A esta operación: Ser congruente con 9883, la voy a llamar (2). Luego:  \( \displaystyle\frac{494.200}{167} \) .  Por la operación (1) multiplico arriba y abajo por  2.960  =  \( \displaystyle\frac{1.462.832.000}{494.320} \) .  Por (2) en el denominador:  \( \displaystyle\frac{1.462.832.000}{170} \) .  Simplifico la fracción entre 10 :  \( \displaystyle\frac{146.283.200}{17} \) .  Por (2) en el numerador tengo:  \( 4.917\cdot\displaystyle\frac{1}{17} \) .  Y ya lo he reducido a un primo inferior al número 201 (aunque éste sea compuesto). Es lo que busco. Ahora ataco al primo:

\( \displaystyle\frac{9884}{17} \) .  Por (1) multiplico por 582 :  \( \displaystyle\frac{5.752.488}{9894} \) .  Por (2) en el denominador:  \( \displaystyle\frac{5.752.488}{11} \) .  Y ya tengo otro primo inferior. Reduzco también el numerador (2) :  \( \displaystyle\frac{582}{11} \) .

Luego hasta ahora tengo:  \( 4917\cdot 582\cdot\displaystyle\frac{1}{11} \) .  Hago la división por si tengo suerte. ¡La tengo! :  260.154. Que congruente Mod 9883 es: 3.196. La respuesta buscada.

Yo creo que esto se puede implementar en un programita por quien quiera hacerlo, aunque es cierto que hay que hacer ciertos "tanteos" entre medias y descartar algunos caminos. Ahí lo dejo.



*Fernando, qué te parece si intentas terminarlo tú (si te apetece); yo lo dejo aquí, lo terminas, y así lo demostramos a medias :)



feriva, yo me he estado dedicando a lo puesto arriba. Yo este tema lo he agotado para mí. A lo que he llegado es a lo de arriba y ya no me interesa. Te repito, lo intenté buscando el absurdo y no lo conseguí. Hace falta la propiedad de ser inverso en un Módulo número primo y para eso está la demostración oficial. De todas maneras es un tema que me ha gustado, a lo mejor vuelvo a él en otra ocasión, más adelante. Ahora quiero seguir un poco más con lo del UTF que lo tengo abandonado por estas cosas. Saludos,
An expert is a man who has made all the mistakes, which can be made, in a very narrow field. Niels Bohr

28 Diciembre, 2019, 06:02 pm
Respuesta #28

feriva

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


feriva, yo me he estado dedicando a lo puesto arriba. Yo este tema lo he agotado para mí. A lo que he llegado es a lo de arriba y ya no me interesa. Te repito, lo intenté buscando el absurdo y no lo conseguí. Hace falta la propiedad de ser inverso en un Módulo número primo y para eso está la demostración oficial. De todas maneras es un tema que me ha gustado, a lo mejor vuelvo a él en otra ocasión, más adelante. Ahora quiero seguir un poco más con lo del UTF que lo tengo abandonado por estas cosas. Saludos,


De acuerdo. Es que yo, en principio, no veía qué era lo que aseguraba eso (aunque conocía la propiedad nunca había pensado en ello) y ahora sí lo veo;  pero no me atrevo a terminar (por no alargarme y no ser demasiado farragoso, no por otra cosa).

En cuanto a tu problema, directamente, como el módulo es primo, por la función phi de Euler el inverso es \( 201^{p-2}
  \); en este caso es un representante muy grande y sería pesado ir hallando por equivalencia representantes más pequeños, pero es el inverso al fin y al cabo (yo prefiero el algoritmo de Euclides, es más de mi estilo, más "álgebra de batalla).

Saludos.

28 Diciembre, 2019, 07:26 pm
Respuesta #29

Fernando Moreno

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


Sin utilizar la propiedad de inversos que tienen los números módulo un número primo. O sea, la propiedad de que se pueden dividir exactamente, no lo vas a conseguir nunca. Me apuesto una super-disculpa por escrito en negrita y de color rosa.

Aquí tienes, por ejemplo, una demostración geométrica del Teorema de Wilson:

https://www.cut-the-knot.org/blue/GeometricWilson.shtml

Aquí un enfoque combinatorio:

http://campus.lakeforest.edu/trevino/WilsonCapsule.pdf

Ah ok. Ahora leo bien esta segunda parte del mensaje de Luis. Pues feriva parece que sí es posible conseguir una demostración sin acudir a la propiedad de la división en los grupos Módulo p. No están a mi alcance. No obstante a lo mejor algún día lo intento otra vez. Es un tema bonito
An expert is a man who has made all the mistakes, which can be made, in a very narrow field. Niels Bohr