Un problema de números primos
Hace unos días Juan Medina, un doctor de matemáticas nos mandaba un problema para que lo pusieramos en el blog, y nos prometía que nos mandaría la solución en un vídeo. Así que sin más dilación os propongo el problema para que lo resolváis a modo de juego:
Demostrar que para todo número primo p distinto de 2 y 5, existe un
número cuyas cifras son todas 9 tal que p lo divide.
Solución dada por Albert
Sea “p” un primo distinto de 2 y de 5. “p” divide un número de la forma 9999999…
En efecto:
99999… (n veces) = 10n - 1
Por el Teorema de Fermat:
10p es congurente con 10 módulo p
Como “p” no divide a 10 (”p” primo y “p” distinto de 2 y 5) por propiedades de las congruencias
10(p-1) es congruente con 1 modulo “p”
o sea 10(p-1) - 1 es congruente con 0 módulo “p”
o sea “p” divide 10(p-1) - 1 [99999… (p-1 veces)]
Podéis observar como todos los pasos que se han hecho aquí son parte de la teoría de números elemental que ya expliqué.
Por cierto, “p” divide a “n” quiere decir que “n” es divisible entre “p”.
Albert | 13 de Noviembre de 2006 | 15:09
Sea p un primo distinto de 2 y de 5. P divide un número de la forma 9999999…
En efecto,
99999… (n veces) = 10^n - 1
Por el Teorema de Fermat,
http://mathworld.wolfram.com/FermatsLittleTheorem.html
10^p és congurente con 10 módulo p
como p no divide a 10 (p primo y p!=2,5) por propiedades de las congruencias
10^(p-1) es congruente con 1 modulo p
o sea 10^(p-1) - 1 es congruente con 0 módulo p,
o sea p divide 10^(p-1) - 1 [99999… (p-1 veces)]
(de hecho esto pasa para muchos más números de la forma 99999… pero hemos encontrado uno para cada p)
Ejemplos:
3 divide a 99,
7 divide a 999999,
11 divide a 9999999999,
13 divide a 999999999999,
etc.
david | 13 de Noviembre de 2006 | 15:42
en los ejemplos algunos son mas faciles:…
3 divide a 9
11 divide a 99
nada, es una chorrada, pero bueno..
^DiAmOnD^ | 13 de Noviembre de 2006 | 15:52
Sí señor, explicación correcta y muy bien explicada. Enhorabuena Albert.
Cada vez resolvéis los problemas antes, estáis hechos unos cracks
Albert | 13 de Noviembre de 2006 | 16:10
Hola David, sí, de hecho hay infinitos. Era para seguir ejemplos de la demostración.
^DiAmOnD^, gracias, este ejercicio me lo pusieron el año pasado en una asignatura llamada Computación Algebraica de primero de Matemáticas de la UPC. Por eso me ha sido tan fácil.
Por cierto felicidades a quien corresponda por la web
soy lector des de hace poco.
neok | 13 de Noviembre de 2006 | 18:32
Sí, señor. ¡Eso es rapidez!
rober | 13 de Noviembre de 2006 | 21:55
¡¡Vaya!! no me ha dado tiempo ni a pensarlo.
Y digo yo, si p no es primo, entonces no se tienen por qué cumplir las congruencias esas. Por ejemplo para 8, 9999999 no es divisible por 8. Bien, pero… ¿es condición necesaria y suficiente para considerar p primo que 10^(p-1)-1 sea divisible por p? sería una prueba de primalidad muy sencilla, digo yo que se le habría ocurrido antes a alguien, así que la pregunta es: ¿cuándo no se da el caso?
Ojo: sí basta para saber que p no es primo en caso de que incumpla la condición ¿servirá para acelerar los algoritmos de búsqueda de primos? ¿y probando con otras bases que no sean 10 = 2×5?
Albert | 13 de Noviembre de 2006 | 23:19
Hola rober, tengo un contraejemplo de lo que comentabas, si no lo he entendido mal.
Por ejemplo se me ocurre el 99 que no es primo (11^1*3^2) y sin embargo cumple la propiedad:
10^98 - 1 son 98 nueves.
Ese numero es divisible por 9 (da 98 unos) y es divisible por 11 (ya que la diferencia de las cifras pares y las impares es 0, multiple de 11) por lo tanto es divisible por 99.
Un saludo!
neok | 13 de Noviembre de 2006 | 23:36
Como te ha dicho Albert el conjunto de números que cumplen esta propiedad es mayor que el conjunto de números primos.
En lo referente a algoritmos de búsqueda de primos, no estoy muy puesto en ese tema, pero creo recordar que actualmente lo mejor que se había conseguido era reducir a una raíz cuadrada el número o algo así y buscar a partir de ahí, me suena de oidas.
^DiAmOnD^ | 13 de Noviembre de 2006 | 23:51
neok ese método es bastante tedioso. Aunque yo tampoco estoy demasiado puesto en el tema he leído por ahí que ahora se usan otros tests de primalidad más completos.
Juan Medina | 14 de Noviembre de 2006 | 2:24
¡¡Enhorabuena Albert!!
Has dado con la demostración que tenía en mente, y por lo tanto, me has evitado tener que grabar el vídeo.
Como veis, el resultado clave en la demostración, es el conocido como “little theorem”, el pequeño teorema de Fermat.
Fermat era abogado y un aficionado a las matemáticas, le gustaba escribir en los márgenes, en uno de los cuales enunció su Fermat’s last theorem:
http://es.wikipedia.org/wiki/%C3%9Altimo_teorema_de_Fermat
que ha llevado varios siglos sin ser demostrado hasta que finalmente obtuvo una demostración Andrew Wiles
http://es.wikipedia.org/wiki/Andrew_Wiles
Fermat dijo que no reproducía la demostración porque no cabía en el margen……
La demostración de este resultado fue publicada en Annals of Mathematics:
http://annals.princeton.edu/
posiblemente, la mejor revista de matemáticas.
Con respecto a los comentarios que hacíais acerca del recíproco del pequeño teorema de Fermat, aquí tenéis una referencia:
http://en.wikipedia.org/wiki/Fermat’s_little_theorem
Como podéis observar, a partir del “little theorem” surge el concepto de pseudoprimos, que son “primos probables”.
Hasta el próximo problema.
^DiAmOnD^ | 14 de Noviembre de 2006 | 2:43
Juan muy interesante el problema, sí señor. Sobre Fermat ya hemos hablado en este blog unas cuantas veces:
Último Teorema de Fermat
Pequeño Teorema de Fermat y números pseudoprimos
Por cierto, enhorabuena por tu iniciativa. Está teniendo un gran éxito por lo que veo. En delicious no hacen más que marcar tu página
rober | 14 de Noviembre de 2006 | 10:39
¡Ups!… pues sí que es cierto que ya se había visto en el blog. En el enlace a Wikipedia se añade que una generalización sirve para la clave de encriptación RSA. El adjetivo de “pequeño” no le queda muy bien ¿no?
Lek | 14 de Noviembre de 2006 | 12:57
Pozí, muy interesante, aunque veo que vais a tener que empezar a proponer cosas más complicadas. Porque este problema a mí me habría llevado muuuuuuucho tiempo, pero tenéis a una legión de “enfermos” hambrientos de matemáticas que os siguen
juanmemol | 14 de Noviembre de 2006 | 15:07
Aunque el RSA sea una enorme herramienta para encriptación, lo bueno que tiene es que es un problema muy sencillo de enunciado. Le pasa lo mismo que con el teorema pequeño de Fermat, sencillo de enunciado y de demostración pero de una aplicación enorme.
Daniel | 16 de Noviembre de 2006 | 23:33
Señores
Después de dos semanas de trabajo, he encontrado una divertida fórmula, que con ciertas dificultades permite describir la serie de los numeros primos, sin saltos entre ellos, por lo tanto es tiempo de descanzar y plasmarlo en lenguaje formal matemático. Quizás sea verdad quizás solo sea una ilusión.
Escribo acá porque en mi busqueda de información para demostrar la fórmula, me encontre con este blog. El lunes contaré si es cierta o falsa mi conjetura, pero de verdad que promete, o por lo menos para mi los numeros primos han dejado de ser una simple distribución aleatoria.
^DiAmOnD^ | 16 de Noviembre de 2006 | 23:53
Daniel si es cierto lo que dices sería un auténtico bombazo. Perdona que desconfíe, pero hasta que no vea esa fórmula no creeré lo que comentas. De todas formas aunque no fuera cierto podría suponer un avance en el estudio de este tema.
Estaríamos encantados de que este blog fuera uno de los sitios donde informaras de tu descubrimiento. Si quieres hasta nos puedes mandar la información por mail (gaussianos [arroba] gamil [punto] com) y publicamos tus resultados.
Saludos
Daniel | 17 de Noviembre de 2006 | 0:34
Lamentablemente acabo de encontrar un grave error en mi conjetura. Pero como es el sueño de todos, aun sigue siendo el mio. Aun el problema de los numeros primos sigue siendo un misterio. Despues de esto creo que voy a buscar por otra via. Esta conjetura no sirve.
^DiAmOnD^ | 17 de Noviembre de 2006 | 0:52
Vaya Daniel, una auténtica pena
. Sigue buscando, como he dicho antes sería un bombazo.
Ánimo y saludos
Albert | 17 de Noviembre de 2006 | 1:39
Daniel los números primos no se distribuyen aleatoriamente. Es facil observar que cada vez son menos frecuentes. Alomejor te interesa echarle un vistazo a esas paginas:
http://mathworld.wolfram.com/PrimeCountingFunction.html
http://mathworld.wolfram.com/PrimeNumberTheorem.html
Saludos
Lek | 17 de Noviembre de 2006 | 17:38
Quizá sea un comienzo, Daniel… es que a la primera no tiene gracia
Daniel | 18 de Noviembre de 2006 | 1:15
Entonces vamos por la segunda.
Pero me parece que mis resultados son demasiado simples.
neok | 18 de Noviembre de 2006 | 1:33
Daniel es que el problema que te has propuesto resolver es de una complejidad enorme, es uno de los grandes, pero como dice Lek no pasa nada porque no hayas conseguido algo a la primera.
Juan Medina | 19 de Noviembre de 2006 | 23:10
Otro problema, muy sencillito y de aplicación de este resultado:
Si p es un primo y n un número natural, n^p-n es un múltiplo de p.
Lek | 21 de Noviembre de 2006 | 13:09
Juan, ¿n puede ser primo?
Juan Medina | 22 de Noviembre de 2006 | 0:48
No tiene porque ser primo, puede ser cualquiera. ¿Podríais proponerlo en un sitio más visible? Parece que los primos triunfan.
^DiAmOnD^ | 22 de Noviembre de 2006 | 1:37
Juan, igual estoy algo espeso pero yo pregunto: ¿ese no es precisamente el enunciado del pequeño teorema de Fermat? Porque si es así no hay nada que demostrar, ¿no?
Juan Medina | 23 de Noviembre de 2006 | 1:44
Efectivamente, olvidé que normalmente es uno de los apartados de la forma habitual de enunciar el teorema pequeño de Fermat. La cuestión es que en mi mente siempre recuerdo éste como:
Si p no divide a, entonces p divide a^(p-1)-1 (*)
y a partir de esto se sigue lo que yo enunciaba:
1. Si p no divide a n, por (*), p divide a n^(p-1)-1 luego también dividirá a esta última cantidad por n, obteniendo lo deseado.
2. Si p divide a n, entonces claramente dividirá a n^p-n porque divide a cada elemento de la resta.
Espero no haber metido la pata.
Juan Medina | 23 de Noviembre de 2006 | 1:48
Otro resultado bonito, que yo planteo como problema en mis hojas de clase:
Si un conjunto X tiene n elementos, tiene 2 elevado a n subconjuntos.
Espero que no haya aparecido anteriormente.
No apto para aquellos que tienen ya la demostración.
^DiAmOnD^ | 23 de Noviembre de 2006 | 3:02
Juan por eso te decía. Yo de hecho conozco como pequeño teorema de Fermat el resultado que tu pusiste como problema.
La demostración del nuevo problema la he visto alguna que otra vez, pero ahora mismo no la recuerdo. En cuanto tenga un rato la busco.
Saludos
Juan Medina Molina | 23 de Noviembre de 2006 | 22:56
No sirve buscarla, hay que pensarla.