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:

Todo número primo pertenece a $M$ .

Existen infinitos números compuestos que pertenecen a $M$ .

Que se os dé bien.

21 comentarios

Sive | 14 de June de 2011 | 08:41

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!!
Trackback | 14 Jun, 2011

Bitacoras.com
josejuan | 14 de June de 2011 | 12:46

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?
Agus | 14 de June de 2011 | 13:42

Idem, Sive.
Sive | 14 de June de 2011 | 16:53

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.
M | 14 de June de 2011 | 17:23

Según 1, ¿hay que demostrar que todo número primo me pertenece? (chiste malo del día).
Pablo M. Paiva | 14 de June de 2011 | 19:27

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
Sive | 14 de June de 2011 | 20:38

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)
josejuan | 14 de June de 2011 | 21:03

“…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).
mimetist | 14 de June de 2011 | 21:10

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.
josejuan | 14 de June de 2011 | 21:19

“…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!
mimetist | 14 de June de 2011 | 21:20

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″.
josejuan | 14 de June de 2011 | 21:22

¡Rápido! edita y duplica todas las barras ( cambia \ por \\ ).
Sive | 14 de June de 2011 | 21:24

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á.
josejuan | 14 de June de 2011 | 21:30

¿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…
mimetist | 14 de June de 2011 | 21:33

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.
gaussianos | 14 de June de 2011 | 22:21

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

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.
Sive | 14 de June de 2011 | 22:53

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…
Diego | 15 de June de 2011 | 02:39

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
cullero | 15 de June de 2011 | 09:38

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.
Javi | 16 de June de 2011 | 04:39

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…