Si divide él, divide el cuadrado

Vamos con el problema de esta semana. Aquí os lo dejo:

Sea M el conjunto de números naturales n que cumplen lo siguiente:

Si n divide a a^n-1, para algún número entero a, entonces n^2 también divide a a^n-1

Demostrar las siguientes cuestiones:

  1. Todo número primo pertenece a M.
  2. Existen infinitos números compuestos que pertenecen a M.

Que se os dé bien.

Share

21 comentarios

  1. Sive | 14 de junio de 2011 | 08:41

    Vótalo Thumb up 0

    Seré piadoso y no reventaré el problema tan pronto, jeje.

    Sólo diré que tengo una demostración de 1), que también es válida para los números de Charmichael, así que demostraría también 2).

    Curiosamente, no recordaba si hay infinitos números de Charmichael o no, y confirmándolo por la web acabé en… ¡¡Gaussianos!!

  2. Trackback | 14 jun, 2011

    Bitacoras.com

  3. josejuan | 14 de junio de 2011 | 12:46

    Vótalo Thumb up 0

    Si es condición necesaria que un número de M cumpla la segunda condición, la segunda condición implica la primera y cumpliendo las dos es suficiente. ¿No basta para definir M indicar la segunda condición?.

    Es decir, M son aquellos n naturales para los que existe algún natural a tal que n^{2} divide a a^{n}-1.

    ¿no?

  4. Agus | 14 de junio de 2011 | 13:42

    Vótalo Thumb up 0

    Idem, Sive.

  5. Sive | 14 de junio de 2011 | 16:53

    Vótalo Thumb up 0

    No te he entendido muy bien josejuan, pero no basta con que exista un número natural a tal que n^2 divida a a^n - 1. Es necesario que siempre que n divida a^n-1, también n^2 lo haga, como dice el título del hilo.

    De hecho, ese matiz es lo que hay que demostrar para los números primos, y un subconjunto infinito cualquiera de los compuestos.

  6. M | 14 de junio de 2011 | 17:23

    Vótalo Thumb up 0

    Según 1, ¿hay que demostrar que todo número primo me pertenece? :D (chiste malo del día).

  7. Pablo M. Paiva | 14 de junio de 2011 | 19:27

    Vótalo Thumb up 0

    Vamos a probar, directamente, que todo número natural pertenece a M:

    Dado un natural n, sea a=(n+1) ¿Será cierto que n^2 (naturalmente, n también lo hará) divide a a^n - 1?

    Tenemos que

    a=(n+1) \Longrightarrow a^n - 1=(n+1)^n - 1

    Luego,

    (n+1)^n - 1 = \displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k}n^{n-k} 1^k - 1 = \displaystyle\sum_{k=0}^n \displaystyle\binom{n}{k}n^{n-k} - 1

    Es fácil ver que el último término de la suma se cancelará con el 1 que está restando, tendremos enconces

    a^n - 1 = (n+1)^n - 1 = \displaystyle\sum_{k=0}^{n-1} \displaystyle\binom{n}{k}n^{n-k}

    Para que n^2 divida a a^n - 1, es necesario que divida a cada uno de los términos de la suma que obtuvimos, cosa que es evidente para los términos hasta k=n-2 ¿Divide n^2 al último término de la suma?

    El término k=n-1 resulta ser

    \displaystyle\binom{n}{n-1}n^{n-(n-1)}=\displaystyle\binom{n}{n-1}n=\displaystyle\frac{n!}{(n-1)!*(n-(n-1))!}*n=\displaystyle\frac{n!}{(n-1)!*1!}*n=\displaystyle\frac{n!}{(n-1)!}*n=\displaystyle\frac{n*(n-1)!}{(n-1)!}*n=n*n=n^2,

    ¡ que es divisible por n^2 !

    En conclusión, todos los términos de la suma son divisibles por n^2 (obviamente, por n también); es decir, que cualquiera sea el natural que elijamos, n y n^2 dividen a al menos un a^n - 1, para algún entero a. Luego, todos los naturales pertenecen a M (con ellos, todos los primos y compuestos, que son infinitos) Q.E.D

  8. Sive | 14 de junio de 2011 | 20:38

    Vótalo Thumb up 0

    Pablo M. Paiva:

    n=9
    a=4

    a^n – 1 = 4^9 – 1 = 262143

    Y 262143 es múltiplo de 9, pero no de 81.

    En el propio contraejemplo se ve que has hecho una suposición que no necesariamente es cierta (que a es de la forma n+1)

  9. josejuan | 14 de junio de 2011 | 21:03

    Vótalo Thumb up 0

    “…Es necesario que siempre que n divida a^{n-1}, también n^{2} lo haga…”

    (Gracias Sive).

    Y puesto que es necesario que eso ocurra, si n^{2} no es divisor entonces no pertenece a M, pero si n^{2} sí es divisor, entonces trivialmente n también es divisor.

    De ahí, que me pregunte si el enunciado es innecesariamente largo o bien (como debe ser para no perder la costumbre) hay algo que no veo (y me gustaría ver, claro).

    De hecho, el intento de Pablo es lo que hace (demostrar sólo la segunda condición).

  10. mimetist | 14 de junio de 2011 | 21:10

    Vótalo Thumb up 0

    Mi intento, (ojalá no sea fallido como cada vez que participo xD):

    Sea p primo de manera que p | a^{p}-1 entonces en aritmética modular:
    a^{p}-1 equiv 0 mod(p), es decir a^{p} equiv 1 mod(p)

    Es fácil ver que, por ejemplo, a = p+1 verifica la congruencia anterior, ya que en este caso:
    a^{p} equiv (p+1)^{p} equiv 1^{p} equiv 1 mod(p)
    Por lo tanto, hemos visto que si p es primo, entonces p in M.

    Ahora, sea n un entero positivo compuesto, entonces existe algún p primo que divide a n… y como hemos visto que p está en M, existe un entero a tal que p|a^{p}-1.

    Como antes, podemos tomar a = p+1 y por lo tanto, como a^{n}-1 equiv 0 mod(p), es evidente que:Ahora, sea n un entero positivo compuesto y tal que su descomposición en factores primos es: n=alpha_{1}^{p_{1}} cdots alpha_{m}^{p_{m}}

    En este caso
    a^{n} equiv a^{p} equiv (p+1)^{p} equiv 1^{p} equiv 1 mod(p)

    Como p divide a n, la misma congruencia es válida módulo n.
    Me dejaba una parte de la demostración!!
    Obviamente, si “p” es mayor que 2, se verifica que p^{2} | a^{p}-1 por las mismas cadenas de congruencias que antes.
    Para “n” compuesto, el caso es análogo por contener algún primo “p” su descomposición.
    cqd.

    Hemos visto así que, como indica Pablo M. Pavia, todos los números enteros pertenecen a M.

    Sive, ten en cuenta que el enunciado dice que “para algún a” se verifica dicha propiedad… es decir, que “existe un a” para el que se verifica la propiedad. En la demostración de Pablo y en la mía se demuestra que siempre existe dicho “a” y que siempre cumple la propiedad de M.

  11. josejuan | 14 de junio de 2011 | 21:19

    Vótalo Thumb up 0

    “…Y 262143 es múltiplo de 9, pero no de 81…”

    Pero Pablo dice que a=n+1 es decir, a=10 y entonces el contraejemplo está mal calculado, de hecho es un ejemplo:

    (n+1)^{n}-1=(9+1)^{9}-1=10^{9}-1=999999999
    999999999/81=12345679

    “…chiste malo del día…”

    A mí me ha hecho gracia (no había caido).

    ¡Acaparador!

  12. mimetist | 14 de junio de 2011 | 21:20

    Vótalo Thumb up 0

    Buenooo… vaya lío con los símbolos… ignorad mi comentario, intenté editarlo y desaparecieron todas las barras que indican los símbolos en latex… he intentado solicitar borrarlo ¡¡y me dice que naranjas de la china!!

    En cualquier caso mi “demostración” no es válida… de hecho no demuestra que p² divida a “(a^n) – 1″.

  13. josejuan | 14 de junio de 2011 | 21:22

    Vótalo Thumb up 0

    ¡Rápido! edita y duplica todas las barras ( cambia \ por \\ ).

  14. Sive | 14 de junio de 2011 | 21:24

    Vótalo Thumb up 0

    Es evidente que el enunciado dice “algún” para no presuponer que existe ese valor de a, pero que hay demostrar que siempre que a^n-1 sea múltiplo de n, también lo es de n^2

    Si el enunciado dijera lo que defiendes, entonces no hay que armar tanto lío.

    Hago a=1, y ya está.

    ;)

  15. josejuan | 14 de junio de 2011 | 21:30

    Vótalo Thumb up 0

    ¿A cambiado el enunciado o el comentario de Sive me ha abierto los ojos? (juraría que el enunciado antes era otro… debo estar muy mal…).

    Ahora pone “Si n divide a a^{n}-1, para algún número entero a, entonces n^{2} también divide a a^{n}-1“.

    Ahora la primera condición exige claramente que la segunda condición se extienda a todos los a válidos en la primera condición (y no sólo en alguno).

    Debo descansar… estoy muy mal…

  16. mimetist | 14 de junio de 2011 | 21:33

    Vótalo Thumb up 0

    josejuan, tienes razón… estaba reescribiendo otra demostración y acabo de caer en la cuenta de lo mismo. Ya no vale probarlo sólo para p+1 o p^{2}+1.

    Muy buen ojo. xD

    Edit: No pude duplicarlas a tiempo :-( … pero para la próxima ya lo tengo aprendido.

  17. gaussianos | 14 de junio de 2011 | 22:21

    Vótalo Thumb up 0

    josejuan, el enunciado no ha cambiado en todo el día. O sea que deberías hacértelo mirar :D.

    mimetist, sí, parece que esa es una solución eventual mientras no encuentre otra forma mejor de editar comentarios: escribir las \ dos veces, ya que al editar se come siempre una.

  18. Sive | 14 de junio de 2011 | 22:53

    Vótalo Thumb up 0

    Según enunciado tenemos que:

    a^n - 1 \equiv 0 \pmod{n}
    a^n \equiv 1 \pmod{n}

    Para algunos valores de a (no necesariamente todos).

    Ahora, si n es primo o un número de Carmichael, sabemos que:

    a^n \equiv a \pmod{n}

    Sin importar el valor de a.

    Igualando con la anterior, tenemos que a \equiv 1 \pmod{n}, es decir, que a es de la forma:

    a = kn+1

    El resto de la demostración es casi un calco de la demostración de Pablo (salvo por el detalle del factor entero k, que no afecta de forma relevante), así que me la voy a ahorrar.

    En realidad esta demostración, con alguna aclaración adicional, para el caso de los compuestos, llega más allá que los números de Carmichael, pero como hoy estoy vago y con eso basta pues…

  19. Diego | 15 de junio de 2011 | 02:39

    Vótalo Thumb up 0

    Si p es primo, entonces p|a^p-1 implica, por teorema de fermat, que p|a-1. Tenemos que p|p=1+1+cdots+1, y 1equiv a, por lo tanto 1equiv a^k, visto modulo p.
    Asi que
    p|1+1+cdots+1=1+a+a^2+cdots+a^{p-1}
    Entonces p^2|(a-1)(1+a+a^2+cdots+a^{p-1})=a^p-1. QED
    Para la segunda parte, considera n=pq, donde p,q son primos.
    pq|a^{pq}-1, entonces p|a^{pq}-1, entonces p|a^q-1, entonces p|p=1+1+cdotsequiv 1+a^q+a^{2q}+cdots+a^{(p-1)q}.
    Mutliplicando las ultimas dos, p^2|a^{pq}-1. Similarmente q^2|a^{pq}-1, porlotanto n|a^n-1. QED

  20. cullero | 15 de junio de 2011 | 09:38

    Vótalo Thumb up 0

    Para variar, seguro que hay algo que se me escapa…

    Se escoge n\in\mathbb{N}. ¿Existe algún a\in\mathbb{Z} tal que n\vert (a^n-1)? Pues sí, el a=1, puesto que 1^n-1=0. En tal caso, además, también se cumple que n^2\vert (1^n-1). Luego M=\mathbb{N}.

    Desde este punto de vista, las afirmaciones 1. y 2., que forman el verdadero problema, son triviales.

  21. Javi | 16 de junio de 2011 | 04:39

    Vótalo Thumb up 0

    Cullero, si te sirve de consuelo yo también había caido en la tentación…

    Con permiso de Sive, te reproduzco el contraejemplo:

    ————————————————————————
    n=9
    a=4

    a^n – 1 = 4^9 – 1 = 262143

    Y 262143 es múltiplo de 9, pero no de 81.
    ————————————————————————

    Vuelve a leer el enunciado y verás como este contraejemplo te descarta el n = 9. Luego ya no son todos los naturales…

Escribe un comentario

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. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.