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”.

Author: fran

32 Comments

  1. 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.

    Post a Reply
  2. en los ejemplos algunos son mas faciles:…

    3 divide a 9
    11 divide a 99

    nada, es una chorrada, pero bueno..

    Post a Reply
  3. Sí señor, explicación correcta y muy bien explicada. Enhorabuena Albert.

    Cada vez resolvéis los problemas antes, estáis hechos unos cracks :)

    Post a Reply
  4. 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.

    Post a Reply
  5. Sí, señor. ¡Eso es rapidez!

    Post a Reply
  6. ¡¡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?

    Post a Reply
  7. 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!

    Post a Reply
  8. 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.

    Post a Reply
  9. 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.

    Post a Reply
  10. ¡¡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.

    Post a Reply
  11. ¡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?

    Post a Reply
  12. 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 ;)

    Post a Reply
  13. 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.

    Post a Reply
  14. 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.

    Post a Reply
  15. 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 :)

    Post a Reply
  16. 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.

    Post a Reply
  17. Vaya Daniel, una auténtica pena :( . Sigue buscando, como he dicho antes sería un bombazo.

    Ánimo y saludos

    Post a Reply
  18. Quizá sea un comienzo, Daniel… es que a la primera no tiene gracia :D

    Post a Reply
  19. Entonces vamos por la segunda.
    Pero me parece que mis resultados son demasiado simples.

    Post a Reply
  20. 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.

    Post a Reply
  21. 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.

    Post a Reply
  22. No tiene porque ser primo, puede ser cualquiera. ¿Podríais proponerlo en un sitio más visible? Parece que los primos triunfan.

    Post a Reply
  23. 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?

    Post a Reply
  24. 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.

    Post a Reply
  25. 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.

    Post a Reply
  26. 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 :)

    Post a Reply
  27. También es interesante la relación que tiene ésto con los números periódicos (en la fórmula/procedimiento, sale “dividir por 999999”, con tantos 9’s como cifras tenga el periodo), y la longitud de dicho periodo.

    Post a Reply
  28. Todos los problema sobre primos deberían tener en cuenta el porqué de su aparentemente extraña sucesió. Este problema ya fue resuelto, al descubrirse que se trata de dos patrones entrecruzados, el segundo de los cuales crece constantemente en proporciones fácilmente deducibles. Así, la aparición de nuevos primos resulta predecible. Aquí la explicación:
    https://ordendenumerosprimos.blogspot.com/

    Post a Reply

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Submit a Comment

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.