La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
domingo, 12 de septiembre de 2010
Problema Del Dia 12 de Septiembre
Si m es impar y n es cualquier numero positivo entero. Encuentra el máximo común divisor de $2^m-1$ y $2^n+1$
Me puse a hecharle talacha y me di cuenta que si elevamos 2 a cualquier potencia impar y le restamos 1, dicho número siempre será primo, entonces el máximo común divisor de 2^m-1 y 2^n+1 es 1.
si M es impar tenemos que siempre qe se eleva el 2 a cualqier potencia impar su ultimo digito va hacer 2 o un 8 entonces $2^m$-1 siempre va terminar en 1 o en 7(cuando m sea impar) del otro lado tenemos que N puede ser cualqier numero entonces los posibles ultimos digitos de $2^n$ = a 2,4,6,8 entonces los ultimos digitos de $2^n$ + 1 = 3,5,7,9 los numeros que se generen siempre de $2^m$-1 y $2^n$+1 van hacer impares por la tanto el MCD tiene qe ser impar despues de ver varios casos llege a esto en el caso de M(impar) $2^1$=2-1=1 $2^3$=8-1=7 $2^5$=32-1=31 $2^7$=128-1=127 $2^9$=512-1=511 $2^11$=2048-1=2047 $2^13$=8192-1=8191 si nos damos cuenta el numero qe nos qede es primo por la tanto sus unicos divisores son 1 y si mismo,,,
en el caso de N $2^1$ = 2+1=3 $2^2$ = 4+1=5 analogamente los proximos resultados seran 9 17 33 65 129 257 513 1025 2049 los resultados de n si pueden ser divididos entre mas numeros. entonces si demostramos que los numeros de la forma $2^n$ +1 nunca van hacer multiplos de los resultados de la forma $2^m$ -1 (que siempre son primos) tendremos qe el MCD es 1 un numero de la manera $2^n$ + 1 no es divisible con un numero de la forma $2^m$ - 1 ,,, porqe los resulados de las segunda forma siempre terminan en 1 o en 7 y los resultados de la primera forma no son divisible con un numero qe termine en 7 o en 1 a exepcionx del 1,,, pero del 11 en delante no,,, por lo tanto tenemos que el MCD = 1
concuerdo con hugo, el otro dia me estuve hasta las 3 de la mañana en un problema, subi la solucion, me aparecio que ya estaba y ena mañana que cheque la pagina otra vez ya no estaba
2^m y 2^n son pares porque solo se van a estar multiplicando por 2 "m" y "n" veces. con esto se sabe q (2^m)-1 y (2^n)+1 son impares.
2^m y 2^n son de la forma 2k entonces (2^m)-1 es de la forma 2k-1 donde m es impar, y (2^n)+1 es de la forma 2k+1(que seria lo mismo que la forma 2k-1).
nose como demostrarlo con formulas o algo asi. pero haber si me hago entender. (2^m)-1 es 1 menos q un multiplo de 2 y (2^n)+1 es 1 mas q un multiplo de 2. y entre ellos no va a haber mcd mayor de 1. enotonces entre ellos el divisor mas grande es el 1.
@ luis carlos yo tambn vi eso q dices de que si elevamos 2 a cualquier potencia impar y le restamos 1, dicho número siempre será primo. pero como sabes si "n" es mayor q "m" por mucho, y un numero primo no puede ser dividido, pero si puede ser multiplicado, y podria llegar a ser ese mismo numero primo el mcd.
complementando mi intento de q entinedan mi solucion: "nose como demostrarlo con formulas o algo asi. pero haber si me hago entender. (2^m)-1 es 1 menos q un multiplo de 2 y (2^n)+1 es 1 mas q un multiplo de 2. y entre ellos no va a haber mcd mayor de 1. enotonces entre ellos el divisor mas grande es el 1."
tambn el q sea mayor por uno q un multiplo de 2, va a ser 1 menos otro multiplo de 2. los dos son impares, pero entre ellos esta esa diferencia par. y no los logra poner en una forma que se puedan dividir entre ellos. y como no se pueden dividir entre ellos su unico mcd es 1.
$2^9 - 1 = 511$ no es primo. Es múltiplo de 7. $511 = 7\times 73$.De hecho es fácil demostrar que para que $2^k - 1$ sea primo $k$ tiene que ser primo. Y no para todos los primos cumple. $2^11 - 1 = 2047$ es $23\times 89$.Les recomiendo tener cuidado cuando decidan que algo es primo. Tienen que checar todos los primos menores a la raíz cuadrada para estar seguros que son primos. Por ejemplo con $511$ deberían checar si $2,3,5,7,11,13,17,19,23$ lo dividen. El hecho que no se den cuenta que $7$ divide a $511$ significa que ni siquiera intentaron verificar que era primo.
@Quique No le entendía a tu comentario pero ya me cayó el veinte. Es cierto que 2^m-1 no siempre va a ser primo, y además, en concordancia con Neil, tambien es cierto que si n es mayor que m, puede llegar a ocurrir el caso de que el mcd sea 2^m-1. Pero al estar buscando el mcd de 2^m-1 y 2^n+1, éste debe ser válido para cualesquiera que sean los valores de m y n, entonces el mcd sí es 1, mi modo de llegar no fue el más adecuado, pero, en mi opinión, sigue siendo correcto. Si le encuentran algún error a mi razonamiento por favor díganme.
en formulas yo supe que el mcd de dos numeros (n,m) es asi: (nm)/mcm(n,m) mcm=minimo comun multiplo y si tomamos el mcm de (2^m-1, 2^n+1)como: (2^m-1)(2^n+1), el minimo comun multiplo seria 1. Todo esto conciderando que el mcm de ambos sea la multiplicaicon de los dos. Ademas los casos que resolvi con 2^m-1 me dieron numeros primos, por lo cual tambien pienso que, si uno es primo, el mcd sea 1
pues tengo que cuando "m" es un numero primo 2^m-1 tambien es un numero primo, y si no es numero primo da un multiplo de 7, y 2^n+1 da multiplos de 3,5 y 17,y 257 que es primo entonces 3,5,7,17 y 257 son primos, entonces para los valores de 2^m-1 y 2^n+1 su maximo comun divisor es 1
Miguel, algunos comentatios: 1) Que $m$ sea primo no significa que $2^m - 1$ sea primo. Por ejemplo $11$ es primo pero $2^{11} - 1$ no es primo. $2^{11} - 1 = 2047 = 23\times 89$.
Tampoco es cierto que si $m$ no es número primo entonces $2^m - 1$ es múltiplo de 7. Por ejemplo $35$ no es primo y $2^{35} - 1 = 31\times 71\times 127\times 122921$ (esos cuatro números son primos y por lo tanto $2^{35} -1$ no es múltiplo de $7$.
Te recomiendo intentar los problemas de calentamiento para tratar de entender el problema un poco mejor.
Hola chamacos, disculpen que no comente anteriormente en el problema. Estoy bastante ocupado. Pero bueno aqui les va un hint casi una solucion pero quiero que hagan los detalles. Vamos a suponer que 2^m-1 y 2^n+1 tienen un divisor primo en comun llamado p. Sea r el numero mas chico tal que p^r es congruente con 1 modulo p. Entonces muestren que r tiene que dividir a m ( usando algoritmo de euclides) y tambien que va a dividir a 2n. pero como 2 y r son primos relatiovos por que r divide a m tenemos que r divide a n. Entonces usando esto vean que 2^n es congruente con 1 modulo p. Pero tambien con -1 lo que significa que p=2 pero esto es absurdo.
que significa gcd ????
ResponderBorrargcd = greatest common divisor = maximo comun divisor = mcd
ResponderBorrarsi m=1
ResponderBorrar2^1-1=1
y pues el mcd seria 1
si m-1>n+1
el mcd es 2^n+1
si n+1>m-1
el mcm es 2^m-1
si m-1=n+1
2^m-1=2^n+1
no se si esta bien, pero pues es lo que se me ocurrio :D
creo que se malentendio el problema, ya le puse $$\LaTeX{}$$ para que se entienda mejor
ResponderBorrarCambie el enunciado para que no sea necesario saber "gcd", estando en México, mejor usamos español.
ResponderBorrarMe puse a hecharle talacha y me di cuenta que si elevamos 2 a cualquier potencia impar y le restamos 1, dicho número siempre será primo, entonces el máximo común divisor de 2^m-1 y 2^n+1 es 1.
ResponderBorrareh estado intentando poner mi solucion! me sale qe ia se subio,,, pero actaulizo el servidor i desparace!
ResponderBorrarsi M es impar tenemos que siempre qe se eleva el 2 a cualqier potencia impar su ultimo digito va hacer 2 o un 8 entonces
ResponderBorrar$2^m$-1 siempre va terminar en 1 o en 7(cuando m sea impar)
del otro lado tenemos que N puede ser cualqier numero entonces los posibles ultimos digitos de $2^n$ = a 2,4,6,8 entonces los ultimos digitos de $2^n$ + 1 = 3,5,7,9
los numeros que se generen siempre de
$2^m$-1 y $2^n$+1 van hacer impares
por la tanto el MCD tiene qe ser impar
despues de ver varios casos llege a esto
en el caso de M(impar)
$2^1$=2-1=1
$2^3$=8-1=7
$2^5$=32-1=31
$2^7$=128-1=127
$2^9$=512-1=511
$2^11$=2048-1=2047
$2^13$=8192-1=8191
si nos damos cuenta el numero qe nos qede es primo por la tanto sus unicos divisores son 1 y si mismo,,,
en el caso de N
ResponderBorrar$2^1$ = 2+1=3
$2^2$ = 4+1=5
analogamente los proximos resultados seran
9
17
33
65
129
257
513
1025
2049
los resultados de n si pueden ser divididos entre mas numeros.
entonces si demostramos que los numeros de la forma
$2^n$ +1 nunca van hacer multiplos de los resultados de la forma $2^m$ -1 (que siempre son primos) tendremos qe el MCD es 1
un numero de la manera $2^n$ + 1 no es divisible con un numero de la forma $2^m$ - 1 ,,,
porqe los resulados de las segunda forma siempre terminan en 1 o en 7 y los resultados de la primera forma no son divisible con un numero qe termine en 7 o en 1 a exepcionx del 1,,, pero del 11 en delante no,,,
por lo tanto tenemos que el MCD = 1
concuerdo con hugo, el otro dia me estuve hasta las 3 de la mañana en un problema, subi la solucion, me aparecio que ya estaba y ena mañana que cheque la pagina otra vez ya no estaba
ResponderBorrarse me hace qe cuando son mui largas se borran automaticamente! porque ahorita ia la dividi en dos partes i no se ah borrado supongo qe puede ser eso
ResponderBorrar2^m y 2^n son pares porque solo se van a estar multiplicando por 2 "m" y "n" veces. con esto se sabe q (2^m)-1 y (2^n)+1 son impares.
ResponderBorrar2^m y 2^n son de la forma 2k entonces (2^m)-1 es de la forma 2k-1 donde m es impar, y (2^n)+1 es de la forma 2k+1(que seria lo mismo que la forma 2k-1).
nose como demostrarlo con formulas o algo asi. pero haber si me hago entender. (2^m)-1 es 1 menos q un multiplo de 2 y (2^n)+1 es 1 mas q un multiplo de 2. y entre ellos no va a haber mcd mayor de 1. enotonces entre ellos el divisor mas grande es el 1.
@ luis carlos
ResponderBorraryo tambn vi eso q dices de que si elevamos 2 a cualquier potencia impar y le restamos 1, dicho número siempre será primo. pero como sabes si "n" es mayor q "m" por mucho, y un numero primo no puede ser dividido, pero si puede ser multiplicado, y podria llegar a ser ese mismo numero primo el mcd.
complementando mi intento de q entinedan mi solucion:
ResponderBorrar"nose como demostrarlo con formulas o algo asi. pero haber si me hago entender. (2^m)-1 es 1 menos q un multiplo de 2 y (2^n)+1 es 1 mas q un multiplo de 2. y entre ellos no va a haber mcd mayor de 1. enotonces entre ellos el divisor mas grande es el 1."
tambn el q sea mayor por uno q un multiplo de 2, va a ser 1 menos otro multiplo de 2. los dos son impares, pero entre ellos esta esa diferencia par. y no los logra poner en una forma que se puedan dividir entre ellos. y como no se pueden dividir entre ellos su unico mcd es 1.
se q me falta algo para concluir, pero la vd ya no se q hacer, no se me ocurre como demostrar lo ultimo. :S
ResponderBorrar$2^9 - 1 = 511$ no es primo. Es múltiplo de 7. $511 = 7\times 73$.De hecho es fácil demostrar que para que $2^k - 1$ sea primo $k$ tiene que ser primo. Y no para todos los primos cumple. $2^11 - 1 = 2047$ es $23\times 89$.Les recomiendo tener cuidado cuando decidan que algo es primo. Tienen que checar todos los primos menores a la raíz cuadrada para estar seguros que son primos. Por ejemplo con $511$ deberían checar si $2,3,5,7,11,13,17,19,23$ lo dividen. El hecho que no se den cuenta que $7$ divide a $511$ significa que ni siquiera intentaron verificar que era primo.
ResponderBorrar2^9-1=511 y 511 no es primo
ResponderBorrar7|511
solo eso encontre hasta ahorita :D
@Quique
ResponderBorrarNo le entendía a tu comentario pero ya me cayó el veinte. Es cierto que 2^m-1 no siempre va a ser primo, y además, en concordancia con Neil, tambien es cierto que si n es mayor que m, puede llegar a ocurrir el caso de que el mcd sea 2^m-1. Pero al estar buscando el mcd de 2^m-1 y 2^n+1, éste debe ser válido para cualesquiera que sean los valores de m y n, entonces el mcd sí es 1, mi modo de llegar no fue el más adecuado, pero, en mi opinión, sigue siendo correcto. Si le encuentran algún error a mi razonamiento por favor díganme.
si m=1
ResponderBorrar2^1-1=1
y pues el unico numero que divide al 1 es el 1
:)
No Luis Carlos. La respuesta depende de $m$ y $n$.
ResponderBorrarPor ejemplo, si el problema fuera:
¿Cuál es la suma de $1+2+3+4+\ldots + n$?.
La respuesta no es $1$ porque con $n = 1$ da $1$. La respuesta es $\frac{(n)(n+1)}{2}$
en formulas yo supe que el mcd de dos numeros (n,m) es asi:
ResponderBorrar(nm)/mcm(n,m)
mcm=minimo comun multiplo
y si tomamos el mcm de (2^m-1, 2^n+1)como:
(2^m-1)(2^n+1), el minimo comun multiplo seria 1.
Todo esto conciderando que el mcm de ambos sea la multiplicaicon de los dos.
Ademas los casos que resolvi con 2^m-1 me dieron numeros primos, por lo cual tambien pienso que, si uno es primo, el mcd sea 1
Eloy, tu solución es incorrecta. No demostraste que el mínimo común múltiplo de $2^m - 1$ y $2^n + 1$ es su producto.
ResponderBorrarpues tengo que cuando "m" es un numero primo 2^m-1 tambien es un numero primo, y si no es numero primo da un multiplo de 7, y 2^n+1 da multiplos de 3,5 y 17,y 257 que es primo entonces 3,5,7,17 y 257 son primos, entonces para los valores de 2^m-1 y 2^n+1 su maximo comun divisor es 1
ResponderBorrarMiguel, algunos comentatios:
ResponderBorrar1) Que $m$ sea primo no significa que $2^m - 1$ sea primo. Por ejemplo $11$ es primo pero $2^{11} - 1$ no es primo. $2^{11} - 1 = 2047 = 23\times 89$.
Tampoco es cierto que si $m$ no es número primo entonces $2^m - 1$ es múltiplo de 7. Por ejemplo $35$ no es primo y $2^{35} - 1 = 31\times 71\times 127\times 122921$ (esos cuatro números son primos y por lo tanto $2^{35} -1$ no es múltiplo de $7$.
Te recomiendo intentar los problemas de calentamiento para tratar de entender el problema un poco mejor.
Hola chamacos, disculpen que no comente anteriormente en el problema. Estoy bastante ocupado. Pero bueno aqui les va un hint casi una solucion pero quiero que hagan los detalles. Vamos a suponer que 2^m-1 y 2^n+1 tienen un divisor primo en comun llamado p. Sea r el numero mas chico tal que p^r es congruente con 1 modulo p. Entonces muestren que r tiene que dividir a m ( usando algoritmo de euclides) y tambien que va a dividir a 2n. pero como 2 y r son primos relatiovos por que r divide a m tenemos que r divide a n. Entonces usando esto vean que 2^n es congruente con 1 modulo p. Pero tambien con -1 lo que significa que p=2 pero esto es absurdo.
ResponderBorrarAh tengo un error de dedo. r es el numero mas chico tal que 2^r es congruente con 1 modulo p.
ResponderBorrarEste comentario ha sido eliminado por el autor.
ResponderBorrar