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

Autor: fran

30 Comentarios

  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.

    Publica una respuesta
  2. en los ejemplos algunos son mas faciles:…

    3 divide a 9
    11 divide a 99

    nada, es una chorrada, pero bueno..

    Publica una respuesta
  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 :)

    Publica una respuesta
  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.

    Publica una respuesta
  5. ¡¡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?

    Publica una respuesta
  6. 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!

    Publica una respuesta
  7. 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.

    Publica una respuesta
  8. 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.

    Publica una respuesta
  9. ¡¡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.

    Publica una respuesta
  10. ¡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?

    Publica una respuesta
  11. 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 ;)

    Publica una respuesta
  12. 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.

    Publica una respuesta
  13. 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.

    Publica una respuesta
  14. 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 :)

    Publica una respuesta
  15. 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.

    Publica una respuesta
  16. Vaya Daniel, una auténtica pena :( . Sigue buscando, como he dicho antes sería un bombazo.

    Ánimo y saludos

    Publica una respuesta
  17. Quizá sea un comienzo, Daniel… es que a la primera no tiene gracia :D

    Publica una respuesta
  18. Entonces vamos por la segunda.
    Pero me parece que mis resultados son demasiado simples.

    Publica una respuesta
  19. 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.

    Publica una respuesta
  20. 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.

    Publica una respuesta
  21. No tiene porque ser primo, puede ser cualquiera. ¿Podríais proponerlo en un sitio más visible? Parece que los primos triunfan.

    Publica una respuesta
  22. 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?

    Publica una respuesta
  23. 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.

    Publica una respuesta
  24. 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.

    Publica una respuesta
  25. 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 :)

    Publica una respuesta

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.

Envía un comentario

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