Enteros positivos con cierta propiedad

Vamos con el problema semanal. Ahí va:

Encuentra todos los enteros positivos n que cumplen que

\cfrac{2^n+1}{n^2}

es un número entero.

A por él.

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.

31 Comentarios

  1. Estoy de acuerdo. Representando f(x) = 2^x + 1 y g(x) = n x^2, con n entero, y buscando los puntos de intersección (dos en la mayoría de los casos) se ve bastante bien.

    Publica una respuesta
  2. al igual que las dos personas de arriba encontré que 1 y 3 son la solución o parte de la solución de la ecuación, creo hay algunos hecho a tomar en cuenta antes de generalizar las soluciones y son las siguientes:

    código-latex-que-quieras-insertar
    \item 2^n>n^2 hecho que se prueba por inducción
    \item debemos ver la paridad de ambos números ya que 2^n es par para todo numero entero, mientras que n^2 puede ser par o impar.
    código-latex-que-quieras-insertar.

    ante la presencia de 1 en la ecuación esto nos indica que deben ser de distinta paridad, lo que obliga a que n siempre debe ser de la forma 2n+1, después usando la congruencia que se obtiene de la expresión original todo se reduce a resolver dicha congruencia hecho en el que me encuentro en este momento

    ahora bien este problema se parece mucho a la conjetura Brocard-Ramanujan

    Publica una respuesta
  3. A falta de demostración formal y dando ya por evidentes los casos n=1,3 lo que sí es fácil de probar es que si n es primo es imposible. También es fácil de ver que el cociente no puede ser un cuadrado (aunque vale de más bien poco). También está claro que módulo n sólo no va a ser suficiente (la congruencia correspondientela verifican infinitos valores de n).

    Publica una respuesta
  4. So fuera el caso de que n primo entonces impossible salta la pregunta the refieres a los primos distintos a 3? Poor que una de las soluciones es 3 el cual evidentemente es primo, lo que so she puede ver as que n nun a puede ser par ya que all dividir par poor par nun a obtenemos residuo 1

    Publica una respuesta
  5. Dije que ya dando por válidas las de n=1,3 no puede ser n primo. En los comentarios que hice obvié en todas los casos n=1,3 porque ya los daba por conocidas. Interprétense como la condición que sea (y no sea con n=1,3).

    Publica una respuesta
  6. A mí esto me suena a una generalización del teorema de Fermat (teorema de Carmichael, según la wikipedia). De hecho, creo que se deduce directamente de ahí que no hay solución para n>3.

    Publica una respuesta
  7. El caso n=1 es trivial, supongamos que n>1 luego n=p_1^{a_1}*p_2^{a_2}*…*p_r^{a_r} con los p_i`s primos diferentes, es suficiente verificar que la congruencia 2^{n} \equiv -1 \pmod{n^{2}} tiene solución; es decir 2^{p_1^{a_1}p_2^{a_2}…p_r^{a_r}} \equiv -1 \pmod{p_1^{2a_1}p_2^{2a_2}…p_r^{2a_r}}, por el teorema chino de los restos es suficiente mirar la congruencia 2^{p_i} \equiv -1 \pmod{p_i^{2}} para cada i ya que m.c.m(p_i^{2a_i},p_j^{2a_j})=1 para i\neq j . Ahora: si 2^{p_i} \equiv -1 \pmod{p_i^{2}} entonces 2^{p_i} \equiv -1 \pmod{p_i} pero por el pequeño teorema de Fermat 2^{p_i} \equiv 2 \pmod{p_i} donde 2 \equiv -1 \pmod{p_i} es decir 3\equiv 0 \pmod{p_i} luego  p_i=3 y entonces se tiene que n=3^{k} con k entero. falta probar que para k>1 la ecuación no tiene solución en enteros

    Publica una respuesta
  8. No me cuadra el paso en el que aplicas el Teorema Chino de los Restos (al menos con la formulación que yo conozco). Podrías detallar esa parte más? Yo del Teorema Chino de los Restos lo único que saco es que al ser corpimos los números que tu dices esa congruencia equivale a un sistema de ellas en módulo p_i^2 (pero no sabría decir la forma de la congruencia), pero no veo de donde sacas que la congruencia sea 2^pi = -1.

    Publica una respuesta
  9. Es más fácil de probar. Es un “descensus ad inferos” (sobre potencias de dos, para pares es trivial que no se cumple)

    Y no doy más pistas 🙂

    Si nadie lo publica antes, intento escribirlo mañana en un hueco, si lo encuentro

    Publica una respuesta
  10. Ahora que mencionad ese hecho, me viene a la mente un metodo descrito en Higher arithmetic escrito por Davenport, en el cual explica un metodo para factorial un numero como producto de primos hace uso de cuadrados.

    Publica una respuesta
  11. Yo tengo algo. Pero hay mal algo en la demostración puesto que no me salta el error n=3. No sé si el fallo es una chorrada de consideración o la lié en algo gordo y la demostración no vale para nada.

    Supongamos que en efecto 2^n = -1 (mod n^2)
    Sabemos por el teorema de Euler que como n no podía ser par 2^phi(n^2)=1 (mod n^2)

    Como phi(n^2)=n*phi(n)

    Sumando ambas expresiones que 2^n(1+2^(n*(phi(n)-1))) es múltiplo de n^2 como n no era par sacamos 2^(n*(phi(n)-1)) = -1 (mod n^2)
    2^n = 1 (mod n^2)

    Repitiendo lo de sumar y factorizar llegamos a que 2^n = -1 (mod n^2) y eso no puede ser.

    El error está en que con 3 ese razonamiemto debería ser posible y no lo es. Consecuentemente he cometido algún error, pero no lo veo y no sé si es una pequeñez salvable o no.

    Publica una respuesta
  12. Nada ya está. Hay un signo cambiado la segunda vez que hago la suma. No vale.

    Publica una respuesta
  13. Buenas noches, ante la falta de claridad y errores de escritura en mi comentario anterior he decido exponer mis ideas nuevamente, pido disculpas por la extensión de la prueba pues no descarto la posibilidad de una más elegante. Sin más preámbulos ahí les va:

    Está claro que para encontrar solución en los enteros es suficiente con hallar las soluciones de la congruencia: 2^{n} \equiv -1 \pmod{n^{2}}, entonces se tienen las siguientes afirmaciones:

    \boldsymbol{i)} n es impar

    \boldsymbol{Dem.} si n fuera par entonces n^{2} también sería par, pero 2^{n}+1 es impar luego n^{2} no divide a 2^{n}+1.

    \boldsymbol{ii)} si n=p^{a} entonces p=3

    \boldsymbol{Dem.} la congruencia: 2^{p^{a}} \equiv -1 \pmod{p^{2a}} claramente implica la congruencia 2^{p^{a}} \equiv -1 \pmod{p} luego aplicando ``a'' veces el pequeño teorema de Fermat sobre ``2^{p}'' tenemos 2^{p^{a}} \equiv 2 \equiv -1 \pmod{p} de donde p=3.

    \boldsymbol{iii)} n no es de la forma n=3^{a}w^{b} donde m.c.d(3,w)=1

    \boldsymbol{Dem.} La prueba es por inducción completa sobre el número r de factores primos de w; consideremos primero el caso w=p primo (distinto de 3)

    \star si n=3^{a}p^{b} con p \neq 3 entonces la congruencia: 2^{3^{a}p^{b}} \equiv -1 \pmod{3^{2a}p^{2b}} implica que 2^{3^{a}p^{b}} \equiv -1 \pmod{p} y de nuevo aplicando reitaradamente el pequeño teorema de Fermat se tiene 2^{p^{b}} \equiv 2 \pmod{p} así 2^{3^{a}p^{b}}=(2^{p^{b}})^{3^{a}} \equiv 2^{3^{a}} \equiv -1 \pmod{p} y así obtenemos elevando al cuadrado que 2^{2*3^{a}} \equiv 1 \pmod{p} ,entonces se tiene que 2*3^{a}\mid p-1 para ver esto supongamos que no y lleguemos a una contradicción. Si  2*3^{a}\nmid p-1 es por que m.c.d(2*3^{a},p-1)=2 ó m.c.d(2*3^{a},p-1)=2*3^{c} con c<a,pues p es impar, y así en el primer caso por la identidad de Bézout existen enteros l,m tales que l*2*3^{a}+m*(p-1)=2 pero se tiene las siguientes congruencias: 2^{2*3^{a}} \equiv 1 \equiv (2^{2*3^{a}})^{l}=2^{l*2*3^{a}} \pmod{p} y 2^{p-1} \equiv 1 \equiv (2^{p-1})^{m}=2^{m*(p-1)} \pmod{p} donde se obtiene, multiplicando las congruencias que 1 \equiv (2^{m*(p-1)})(2^{l*2*3^{a}})=2^{l*2*3^{a}+m*(p-1)}=2^{2} \pmod{p} por lo que de nuevo p=3 contradicción.

    Para el segundo caso si m.c.d(2*3^{a},p-1)=2*3^{c} con c<a entonces por la identidad de Bézout nuevamente, tenemos: l*2*3^{a}+m*(p-1)=2*3^{c} y se tienen las siguientes congruencias 2^{2*3^{a}} \equiv 1 \equiv (2^{2*3^{a}})^{l}=2^{l*2*3^{a}} \pmod{p} y 2^{p-1} \equiv 1 \equiv (2^{p-1})^{m}=2^{m*(p-1)} \pmod{p} donde se obtiene, multiplicando las congruencias que 1 \equiv (2^{m*(p-1)})(2^{l*2*3^{a}})=2^{l*2*3^{a}+m*(p-1)}=2^{2*3^{c}} \pmod{p} y aplicando el mismo razonamiento con c al igual como se hizo con a (descenso infinito) se tiene una cadena decreciente de enteros no-negativos que tiene que detenerse en 0, 0<…<c<a pero entonces p=3 y se tiene la contradicción.

    \star para terminar con la prueba de la afirmación hagamos w=\prod_{i=1}^{r}p_i^{b_i} con los p_i`s primos distintos entre si (y diferentes a 2 y a 3) y supongamos que hemos probado que n no puede ser de la forma n=3^{a}\prod_{i=1}^{j}p_i^{b_i} para todo j<r, entonces tenemos: la congruencia 2^{3^{a}\prod_{i=1}^{j}p_i^{b_i}} \equiv -1 \pmod{3^{2a}\prod_{i=1}^{j}p_i^{2b_i}} implica que 2^{3^{a}\prod_{i=1}^{j}p_i^{b_i}} \equiv -1 \pmod{p_k} para todo 0<k<j+1, pero 2^{p_k^{a_k}} \equiv 2 \pmod{p_k} así 2^{3^{a}\prod_{i=1}^{k-1}p_i^{b_i}\prod_{i=k+1}^{j}p_i^{b_i}} \equiv -1 \pmod{p_k}

    Publica una respuesta
  14. como antes se tiene que 2^{2*3^{a}\prod_{i=1}^{k-1}p_i^{b_i}\prod_{i=k+1}^{j}p_i^{b_i}} \equiv 1 \pmod{p_k} implica 2*3^{a}\prod_{i=1}^{k-1}p_i^{b_i}\prod_{i=k+1}^{j}p_i^{b_i} \mid {p_k-1} pues siguiendo con los razonamientos como antes se tiene: si 2*3^{a}\prod_{i=1}^{k-1}p_i^{b_i}\prod_{i=k+1}^{j}p_i^{b_i} \nmid {p_k-1} es por que bien m.c.d(2*3^{a}\prod_{i=1}^{k-1}p_i^{b_i}\prod_{i=k+1}^{j}p_i^{b_i},p_k-1)=2 ó bien m.c.d(2*3^{a}\prod_{i=1}^{k-1}p_i^{b_i}\prod_{i=k+1}^{j}p_i^{b_i},p_k-1)=2*3^{c}\prod_{i=1}^{k-1}p_i^{d_i}\prod_{i=k+1}^{j}p_i^{d_i} con c\leq a y d_i\leq b_i para todo i, donde además para algún h, d_h<b_h o bien c<a aplicando el mismo razonamiento pero ahora con la j-tupla (c,d_1,…,d_{k-1},d_{k+1},…,d_j) tantas veces como sea necesario se tiene que al menos un d_g se ha reducido a 0 en donde aplicamos la hipótesis de inducción (pues tiene un factor primo menos) y se tiene la contradicción o c se ha reducido a 0, en este último caso tendríamos una congruencia del tipo : 2^{2*\prod_{i=1}^{k-1}p_i^{e_i}\prod_{i=k+1}^{j}p_i^{e_i}} \equiv 1 \pmod{p_k} y vamos a probar ahora que este caso se reduce al anterior anterior

    Publica una respuesta
  15. Me he basado en la pista que dio “josera”.
    Empezamos con que la expresión 1) 2^{n} = k*n^{2} - 1 debe cumplirse para k y n enteros positivos. Es trivial que tanto k como n deben ser impares por lo que podemos escribir k=2*k_1+1 y n=2*n_1+1. Para n_1=0 o k_1=0 conocemos las soluciones, así que vamos a suponer que n_1 \neq 0 y k_1 \neq 0 y vamos a ver si hay alguna solución que pueda cumplir estas condiciones.
    Si sustituimos las expresiones de k y n en la expresión 1) y operamos obtenemos 2) 4^{n_1}=2*(2*k_1+1)*n_1^{2}+2*(2*k_1+1)*n_1+k_1
    De esta expresión se deduce que n_1 debe ser par y k_1 debe ser divisible entre 4. Por tanto \exists n_2 \setminus n_1=2*n_2 y \exists k_2 \setminus k_1=4*k_2.
    Si sustituimos estas expresiones en 2) llegamos a la expresión 3) 16^{n_2}=8*(8*k_2+1)*n_2^{2}+4*(8*k_2+1)*n_2+4*k_2.
    Pero de nuevo se deduce que n_2 y k_2 deben ser pares los dos, y que deben existir n_3 y k_3 tales que n_2=4*n_3 y k_2=4*k_3. Se puede observar que este proceso no se detiene nunca, y que para admitir que n_1 \neq 0 y k_1 \neq 0 deberíamos admitir también que hay una sucesión infinita descendente de números pares, empezando desde uno dado, lo que nos lleva a la conclusión de que n=3 y n=1 son las dos únicas soluciones posibles.

    Publica una respuesta
  16. Dices:

    De esta expresión se deduce que n_1 debe ser par y k_1 debe ser divisible entre 4.

    ¿Puedes explicar por qué?

    Publica una respuesta
  17. Me acabo de dar cuenta de que la demostración está mal. Golvano, ese paso que preguntas es el que falla. Pensé que lo tenía.

    Publica una respuesta
  18. Me parece que lo tengo:
    Partimos de 2^n=Kn^2-1, con n y K naturales.

    Reescribimos n y K de otro modo:
    n=(\sum_{i=1}^{M_n} a_i\cdot 2^i)+1; M_n \le \lfloor \log_2 n \rfloor; a_i \in \{ 0,1\}

    K=(\sum_{k=1}^{M_K} b_k\cdot 2^k)+1; M_K \le \lfloor \log_2 K \rfloor; b_k \in \{ 0,1\}

    Sustituimos n y K por sus expresiones y obtenemos:
    2^n=Kn^2-1=\sum\sum {a_i}^2 b_k\cdot 2^{2i+k}+\sum\sum\sum a_i a_j b_k\cdot 2^{i+j+k+1}+\sum\sum a_i b_k\cdot 2^{i+k+1}+\sum b_k\cdot 2^k+\sum {a_i}^2\cdot 2^{2i}+\sum\sum a_i a_j\cdot 2^{i+j+1}+\sum a_i\cdot 2^{i+1}

    Para abreviar lo expresaremos así:
    2^n=Kn^2-1=S_{2i+k}+S_{i+j+k+1}+S_{i+k+1}+S_k+S_{2i}+S_{i+j+1}+S_{i+1}

    Ahora el razonamiento es el siguiente: la expresión anterior es una suma de potencias de 2. Una suma de potencias de 2 no puede dar como resultado una potencia de 2 (2^n) a no ser que los exponentes de los sumandos sean todos iguales.

    Si nos fijamos en los tres últimos sumandos, S_{2i},S_{i+j+1},S_{i+1} se observa que la única forma de que todos tengan el mismo exponente es que M_n\le 1.

    Si M_n=1 hay que fijarse en los cuatro primeros sumandos para concluir que si se desea que todos tengan el mismo exponente en 2 entonces M_K=0 lo que lleva a la solución n=3 y K=1.

    Si M_n=0 sólo queda el sumando \sum b_k\cdot 2^k lo que en principio no lleva a ninguna restricción sobre M_K pero con un simple cálculo se obtiene la única solución k=3.

    Con esto quedaría demostrado que sólo son posibles las soluciones n=1 y n=3 y ninguna otra más.

    Publica una respuesta
  19. Estoy intrigado por los + 1 que salen de poner n y K en su forma binaria.

    También me intriga la frase de que una suma de potencias de 2 no da como resultado otra potencia de 2 (cierto) a no ser que los exponentes de dichos sumandos sean iguales (????? No tiene por qué, según mi parecer, ejemplo: 2^k + 2^k + 2^k = 3·2^k… Si el número de sumandos fuera una potencia de 2 aún). Luego de ahi, además tomas porque sí los tres últimos sumandos. Finalmente, también hay varias afirmaciones sobre Mn o Mk sin demostrar, etc.

    A lo mejor es correcta la demostración y todo, pero no sé de dónde concluyes ciertas cosas.

    Publica una respuesta
  20. Featuring, me explico:
    los +1 son porque tanto n como K deben ser impares. Lo explican más arriba pero es fácil de ver que si uno de los dos (o ambos) fueran pares 2^n=K\cdot n^2-1 sería impar y no podría ser igual a una potencia de 2.

    En lo segundo que dices llevas razón. Quizá me explique mejor si digo que una condición NECESARIA para que una suma de potencias de dos de como resultado una potencia de dos es que todas tengan el mismo exponente. Es decir, que si encontramos una prueba de que no se cumple esa condición estaremos seguros de que no pueden sumar 2^n, y eso aunque no conozcamos exactamente el número de sumandos ni sus valores precisos.

    A continuación me centro en los tres últimos sumandos para encontrar qué condiciones deben cumplir esos tres sumandos para que siempre tengan el mismo exponente. Aunque, siendo estrictos, en realidad sólo hacía falta fijarse en dos de ellos: S_{2i} y S_{i+1}. Me fijo en ellos sólo porque no tienen b_k, así que sólo me tengo que centrar en cómo son los a_i, es decir, tomo una parte más sencilla de analizar para luego abordar el problema entero.

    Seguidamente encuentro que si M_n>1 entonces seguro que los exponentes son diferentes, con lo que ya no haría falta seguir mirando qué sucede con el resto de sumandos (ya hay dos sumandos que no cumplen la condición necesaria). ¿Por qué los exponentes salen diferentes si M_n>1? Porque si te fijas: 2i>i+1 si i>1, es decir si el máximo i que aparezca en la expresión de M_n es mayor que 1 entonces seguro que aparecerán exponentes diferentes.

    Una vez probado que M_n\le 1 deduzco con los sumandos que me quedan que M_K=0. En esta deducción reconozco que me he equivocado, pero no afecta a la demostración general, simplemente hay que ver que M_n=1 \rightarrow n=3 \rightarrow K=1. Por otro lado ya se ha comprobado que como M_n\le 1 y n es impar entonces n \le 3 que es lo que demuestra que sólo hay dos soluciones posibles.

    Finalmente imagino que las afirmaciones sobre M_n=\max\{i\setminus a_i=1\} y \max\{k\setminus b_k=1\} son las que necesitan explicación. Lo explico para M_n porque para M_K es igual (y además es un valor que no llego a usar). La idea es que M_n es la máxima posición que tiene un 1 en la representación binaria de n. Es necesario definirlo porque durante la demostración me sirvo de ese valor para deducir por qué M_n\le 1.

    Espero haber aclarado algo.

    Publica una respuesta
  21. Miguel Angel, tu “condición NECESARIA para que una suma de potencias de dos de como resultado una potencia de dos es que todas tengan el mismo exponente” no parece creíble: 2^2+2^2+2^3=2^4. O algo no he entendido o tu redacción de la condición es errónea o incompleta.

    Publica una respuesta
  22. Los únicos valores posibles para n son 1 y 3, aquí va mi solución: asumimos que n > 1.

    Decir que \frac{2^{n} + 1}{n^{2}} sea un natural es equivalente a decir que 2^{n} +1 \equiv 0 \quad (\mod n^{2})

    2^{n} \equiv -1 (\mod n^{2}) \quad \Rightarrow \quad 2^{2n} \equiv (-1)^{2} = 1 \quad (\mod n^{2}) \quad \Rightarrow \quad \phi (n^{2}) | 2n

    Ahora utilizamos tres observaciones:
    1. n ha de ser IMPAR, de otra manera el cociente \frac{2^{n} + 1}{n^{2}} no podría ser un natural al ser impar el numerador.

    2. n, natural positivo, siempre divide a \phi (n^{2}) (seguro?)

    3. m\geq 3 \Rightarrow \phi(m) es par.

    Con estas tres observaciones queda claro que \phi(n^{2}) = 2n ya que n| \phi(n^{2}) |2n.

    Ahora veremos que, además de la solución trivial, la única solución es n = 3.

    n = \prod_{i = 1}^{i = r} p_{i}^{a_{i}} la factorización en números primos para n. Entonces

    \phi (n^{2}) = \phi (\prod_{i = 1}^{i = r} p_{i}^{2a_{i}} ) = \prod_{i = 1}^{i = r} \phi( p_{i}^{2a_{i}} ) = \prod_{i = 1}^{i = r} p_{i}^{2a_{i} -1} (p_{i} - 1)

    Observamos que basta con que haya un primo distinto de 3 en la factorización de n para que \phi (n^{2})  >  2n. Por tanto n ha de ser una potencia de 3.

    Pero \phi (3^{2a}) = 3^{2a - 1} 2 = 2*3^{a} 3^{a-1} de donde deducimos que a = 1. De esta forma, además de 1, la única solución es 3.

    Publica una respuesta
  23. Danielsan, no necesariamente  a^{k} \equiv 1 \, \, ( mod \, m)  implica   \phi(m)|k

     2^{3} \equiv 1 \,\, ( mod \, 7)  , pero no es cierto que   6|3

    Si pudiésemos demostrar que el orden de 2 en  \mathbb{Z}_{n^2} es  \phi(n^2) , entonces tendríamos   \phi(n^2)= n \phi(n) \, | \, 2n  \Rightarrow   \phi(n) |2 \Rightarrow \phi(n)=1,2   \Rightarrow     n=1,2,3,4,6 \Rightarrow  n=1,3  .

    Publica una respuesta
  24. No es verdad que el orden de 2 en \mathbb{Z}_{n^2} sea \phi(n^2) . Por ejemplo, para n=7, el orden de 2 es 21, no 42.

    Publica una respuesta
  25. Es verdad Karl, muchas gracias.
    He asumido que el orden de 2 en \left(  \frac{ \mathbb{Z} }{ n^2} \right)^* es el orden de todo el grupo… Vaya, qué desilusión 🙁

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Vamos con el problema semanal. Ahí va: Encuentra todos los enteros positivos que cumplen…

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 *