Si divide él, divide el cuadrado

Publicado por ^DiAmOnD^ | 14 junio, 2011 | Juegos | 20 |

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.

0 0 votes

Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉

Sobre el Autor

^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook. También tengo un blog dedicado a las "escape rooms", por si te apetece pasarte: XRooMers.

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.

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

20 Comments

más antiguo

más reciente más votado

Inline Feedbacks

View all comments

Sive

14/06/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!!

Responde

Bitacoras.com

14/06/2011 12:38

Información Bitacoras.com…

Valora en Bitacoras.com: Vamos con el problema de esta semana. Aquí os lo dejo: Sea el conjunto de números naturales que cumplen lo siguiente: Si divide a , para algún número entero , entonces también divide a Demostrar las siguientes cuestiones……

Responde

josejuan

14/06/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?

Responde

Agus

14/06/2011 13:42

Idem, Sive.

Responde

Sive

14/06/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.

Responde

14/06/2011 17:23

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

Responde

Pablo M. Paiva

14/06/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 (naturalmente, n también lo hará) divide a ? Tenemos que Luego, Es fácil ver que el último término de la suma se cancelará con el 1 que está restando, tendremos enconces Para que divida a , 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 ¿Divide al último término de la suma? El término resulta ser , ¡ que es divisible por ! En conclusión, todos… Lee más »

Responde

Sive

14/06/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)

Responde

josejuan

14/06/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).

Responde

mimetist

14/06/2011 21:10

Mi intento, (ojalá no sea fallido como cada vez que participo xD): Sea p primo de manera que entonces en aritmética modular: , es decir Es fácil ver que, por ejemplo, verifica la congruencia anterior, ya que en este caso: Por lo tanto, hemos visto que si p es primo, entonces . 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 . Como antes, podemos tomar y por lo tanto, como , es evidente que:Ahora, sea n un… Lee más »

Responde

josejuan

14/06/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!

Responde

mimetist

14/06/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».

Responde

josejuan

14/06/2011 21:22

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

Responde

Sive

14/06/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á.

😉

Responde

josejuan

14/06/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…

Responde

mimetist

14/06/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.

Responde

gaussianos

Admin

14/06/2011 22:21

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.

Responde

Sive

14/06/2011 22:53

Según enunciado tenemos que: Para algunos valores de a (no necesariamente todos). Ahora, si n es primo o un número de Carmichael, sabemos que: Sin importar el valor de a. Igualando con la anterior, tenemos que , es decir, que a es de la forma: 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… Lee más »

Responde

Diego

15/06/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

Responde

cullero

15/06/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}$ .