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

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor del blog Gaussianos. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

20 Comentarios

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

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

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

    Publica una respuesta
  4. Según 1, ¿hay que demostrar que todo número primo me pertenece? 😀 (chiste malo del día).

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

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

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

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

    Publica una respuesta
  9. “…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!

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

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

    😉

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

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

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

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

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

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

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

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Vamos con el problema de esta semana. Aquí os lo dejo: Sea el conjunto…

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 *