¿Cuántos racionales de la forma $\large \frac{2^n+1}{n^2}$ son números enteros?

Question

Este era el Problema 3 (primer día) de la década de 1990 de la OMI. Una solución completa se puede encontrar aquí.

Cuántos racionales de la forma $\large \frac{2^n+1}{n^2},$ $(n \in \mathbb{N} )$ son enteros?

Los posibles valores de $n$ que soy capaz de encontrar es$n=1$$n=3$, por lo que hay dos soluciones, y esta parece ser la respuesta a este problema.

Pero ahora tenemos que demostrar que no más de ese $n$ existe, y por lo tanto la prueba se reduce a: Demostrando que $n^2$ no divide $2^n+1$ cualquier $n \gt 3$.

¿Alguien sabe cómo demostrarlo?

Answer 1

Este fue el problema 3 (primer día) de la OMI de 1990. Una solución completa se puede encontrar aquí.

Answer 2

Es un poco tarde para publicar esta respuesta. Pero me he encontrado con esta pregunta puede ser resuelto mediante la Elevación de la exponente lema con tanta facilidad.

Teorema: Vamos a $x$ $y$ ser dos enteros y $n$ es un entero impar. Deje $p$ ser un od primer tales que $p|x+y$ y ninguno de $x$ $y$ son divisibles por $p$. Entonces tenemos,

$v_p(x^n+y^n)=v_p(x+y)+v_p(n)$

$v_p(N)$ denota el mayor poder de $p$ que se divide $N$.

Solución:

Reclamo: Si $n$ divide $2^n+1$ $n$ es un poder perfecto de $3$.

Prueba:

Deje $p$ ser un menor factor primo de $n$,

Eso significa que $2^n \equiv -1 \pmod p \implies 2^{2n} \equiv 1 \pmod p$. Y también se $2^{p-1} \equiv 1 \pmod p \implies 2^{\gcd(2n,p-1)} \equiv 1 \pmod p$

Ahora, desde la $p$ es el menor divisor de $n$$\gcd(2n,p-1)=2 \implies 2^2 \equiv 1 \pmod p \implies p=3$, por lo tanto, $n=3^m \cdot k \text { and } 3 \nmid k$ si $k$ es mayor que $1$, el argumento similar se mostraría $3 |k$. Contradicción.

Así que tenemos $3^{\alpha} || n \implies 3^{\alpha+1} \nmid n $

$v_3(2^n+1) \ge v_3(n^2)$

$v_3(2+1)+v_(n) \ge v_3(n^2)$

$1+ \alpha \ge 2\alpha \implies \alpha =1,0$

$\implies v_3(n)=1,0$

$n=1 \text{ or } 3$

Answer 3

Andre modificación de una respuesta incorrecta :)

Si $n=3^k$, luego

$$2^n+1=2^{3^k}+1=2^{3 \cdot 3^{k-1}}+1= (2^{3^{k-1}}+1)( 2^{2 \cdot 3^{k-1}}-2^{ \cdot 3^{k-1}}+1) $$

El segundo soporte nunca es divisible por $9$, con lo que por inducción se puede probar que $3^{2k-1}$ no divide $2^n+1$.

Nota: Ya que Geoff respuesta es incorrecta, y este post no tiene mucho sentido, una simple observación:

Si $n \neq 1$,$3|n$.

De hecho, vamos a $p$ ser el menor divisor primo de $n$.

A continuación,$2^{p-1} \equiv 1 \mod p$$2^{2n} \equiv (-1)^2 \equiv 1 \mod p$.

Por lo tanto $2^d \equiv 1 \mod p$ donde $d=gcd(p-1,2n)$. Pero no el primer factor de $p-1$ puede dividir $n$, ya que el $p$ es la más pequeña, por lo tanto $gcd(p-1,n)=1$. Por lo tanto $d |2$.

$2^d \equiv 1 \mod p$ implica que ahora que $p=3$.

Esto demuestra que $n=3^km$ algunos $k \geq 1$ $m $ relativamente primer a $3$. Me pregunto si el primer argumento puede ser modificado para este caso:

$$2^n+1=2^{3^km}+1=2^{3 \cdot 3^{k-1}m}+1= (2^{3^{k-1}m}+1)( 2^{2 \cdot 3^{k-1}m}-2^{ \cdot 3^{k-1}m}+1) $$

Desde $9$ no dividen el segundo soporte de conseguir que la $3^{2k-1}$ debe dividir $(2^{3^{k-1}m}+1)$ y repitiendo pienso que llegamos $3^{k}$ divide $2^m+1$...

Es fácil probar que $2^m \equiv -1 \mod 9$ implica $3 |m$ (esto se deduce de la $2^3 \equiv -1 mod 9$$ord(2)=6$).

Por lo tanto $k=1$, y debemos tener $n=3 m$ $gcd(3,m)=1$...

Ahora, vamos a intentar de nuevo la misma.

Supongamos por contradicción $m \neq 1$. Deje $q$ ser el menor factor primo de $m$.

Entonces

$2^d \equiv 1 \mod q$ donde $d=gcd(q-1,2n)$. Pero no el primer factor de $p-1$ puede dividir $n$, a excepción de la $3$, por lo tanto $d |6$.

Esto implica que

$$2^6 \cong 1 \mod q \,.$$

Por lo tanto, los únicos valores posibles de $q$$q=7$.

Pero esto no es posible ya $2^{3m}+1 \equiv 1+1 \mod 7$, lo $7$ no se puede dividir $2^n+1$.

Answer 4

He traducido el manejo del problema en una determinada notación, que me parece muy útil para el formal de la manipulación algebraica de los exponencial diophantine problemas, y proporcionar una solución en la que el formalismo. El Woeginger-solución ya estaba vinculado por André Nicolas así que mi propuesta manera de resolver esto ahora es sólo para que el lector que podría estar interesado en que -espero-de: general - formalismo. Aquí está el enlace hasta el momento. (Soy un poco perezoso para codificar el texto en latex/mathjax aquí después de la original jugueteando con word/word a pdf. Tal vez yo pueda ponerlo en mathjax después del fin de semana, si no hay ningún interés en absoluto)

Answer 5

Es interesante que todo el mundo está teniendo en cuenta que $n$ debe ser un primo. $2^{55}+1$ $55^2$ comparten un factor común de $121$, ya que al $n$ es compuesto, no hay ninguna necesidad de que el período de dividir a $n-1$.

Uno puede ver que $n$ no puede ser, porque el primer número será impar, y el divisor incluso. Así, los números que se dividen algunos $2^e+1$, dejar un resto de '3' o '1', cuando se divide por 8. En el ejemplo anterior, $121$$11^2$, y el 11 es 3 modulo 8.

Así, por ejemplo, $171$ divide $2^{171}+1$, e $171^2$ divide $3 \cdot(2^{171}+1)$.

No podría existir en varios de los números primos, de la forma $p=1,3 \mod 8$, en el período que se divide el producto, y por lo tanto satisfacer completamente a esta relación. La prueba de 'crianza de los poderes' no impide el caso de 2, como se muestra en los ejemplos de $55$ $171$ arriba, de donde uno proviene de los múltiples de $11$, e $19$, y el otro viene desde el período básico.

General de la Prueba de $n^2 \mid b^n+1$

$1$. $n$ es extraño que todos los $b$

Supongamos $n$ es incluso, decir $n=2e$, luego tenemos a $4 \mid 4e^2 \mid b^{2e}+1$. Sin embargo, el último término es nunca un múltiplo de $4$, lo $n$ debe ser impar.

$2$. La regla de descenso.

Supongamos que $p \mid n$$p \mid b^q+1$,$q \mid n$.

Esto es debido a que $p \not\mid b^x+1$ si $q \mid x$. q es 1, o tiene la primera divisores. Poner $p'$, $q'$ para cada divisor de $q$, y repetir.

$2a$ La regla de ascenso.

Si por alguna $p \not\mid n$, que su $q \mid n$, $pn$ es una solución.

Esto se utiliza para ascender desde las instancias donde $q=1$ es decir $p \mid b+1$, como de la construcción en general en los lugares permitidos.

$3$ Regla de sevenites y repetidores.

Si $p^m \mid n$,$p^m \mid (b^n+1) /(b^q+1)$, y para$p^{2m} \mid b^n+1$,$p^m \mid b^q+1$.

Si $p \mid b^x+1$$p \mid (b^{px}+1 )/(b^x+1)$. Este e $b^g+1 \mid b^{gh}+1$ por extraño $g, h$, significa que si $p^m \mid n$$p^n \mid (b^n+1)/(b^q+1)$.

$p \mid (b^{px}+1)/(p^x+1)$ repite algunas $p$ antes. Es fácil mostrar que $p^2$ no trabajo aquí, excepto en un caso de $p=2$. Esto significa que si $p^m \mid n$, entonces es necesario que $p^m \mid b^q-1$. Los repetidores son la razón por la $p^m$ puede tener períodos. Por ejemplo, 3 tiene 2 dígitos para el período en base 2, y 9 tiene un 6 dígitos del período, y el 27 de 18 dígitos período.

Un sevenite es donde si $p \mid b^n-1$, entonces también lo hace $p^2$. Ver enlace abajo para sevenites a bases de $2112$$p<144000$.

http://z13.invisionfree.com/DozensOnline/index.php?showtopic=737

Discusión

Vemos que la regla de descenso significa que sólo es necesario empezar a partir de los divisores de a $b+1$, lo que dará $q=1$. A continuación, consideramos que los divisores de $b^x+1$ donde $x$ es un divisor impar de $b+1$. Esto significa que $3, 7, 15, 31, \cdots$ no tiene más de acción, porque no hay impar de divisores > 1.

Para $b=10$, podemos ver que $b+1=11$, $10^{11}$ tiene divisores $11^2 \cdot 23 \cdot 4093 \cdot 8779$. El producto de $11$, y a cualquiera de estos números primos >11, satisface esta relación. También vemos que por la regla de descenso, si $47$, $23$ también debe dividir $n$. De hecho, 23 trae en $47, 139, 2531$. $139$ a su vez trae en $557$$2503$. La regla de descenso se aplica aquí. Así que si $2531$ divide $n$$n^2 \mid 10^n+1$, por lo que debe 23, 11. Por lo $640343$ es una solución. Puede ser multiplicado por $139$ o $47$ o $4093$ o $8779$, debido a que las trayectorias de descenso ya están allí.

   1    11
  11    23   4093  8779
  23    47   139   2531  
  47   6299
 139    557 2503  

Al $b+1$ es compuesto, como en $b=14$, uno puede bajar a cualquier de los divisores de a $b+1$. Esta es la tabla de descenso,$b=14$. Como antes, los números a la derecha se $p$ tener la primera como su $q$.

   1    3   5
   3    61
   5    71  101
  15    811
  61    90281
  71    569  3620291
 183    733  9151
 213    1287799

El marcador ejemplo aquí es $80$ donde $80+1=3^4$. amd $80^3+1 = 3^5\cdot 7^2 \cdot 43$. Uno de los tres en $80^3+1$ es un repetidor, pero esto significa que cualquier primer cuyas $q$ trata de un divisor de a $3^4 7^2 43$ puede ser inmediatamente se multiplica para dar un adicional de solución. Específicamente $127 (q=21)$, $163 (q=81)$ y $883 (q=441)$ todo el trabajo, como cualquier numner $3 | n | 3^4 7^2 43$. Estos, y varios de los números primos muy grandes, todo el trabajo en base a $80$, con la norma habitual de descenso.

    1    3  3 3 3
    3    7  7  43
    7    29  4789 ..
   21    127  ...
   43    1721
   81    163

La regla de descenso se produce un error en $b=2$

Cuando comenzamos con $2$,$2+1=3$, lo que nos permite considerar los factores de $2^3+1$, otros de $3$. Pero no hay ninguno de los factores.

Podríamos tratar de seguir la regla de descenso, señalando que si $n$ es impar, entonces cualquier prime que divide $n$ debe $1, 3$ mod $8$. La lista comienza $3$, $11$, $17$, $19$, $41$, $43$, $67$. Si bien $p$ o de sus derivados $q$ no es factorised a esta lista, podemos huelga.

Vemos aquí la importancia de la prueba para $55$ $171$ en los posts anteriores. Ambos de estos trabajos para la mayor prime, pero no sobre el descenso. Esta es la magia aquí. Sus caminos están rotos, pero nos abren el camino para una posible ininterrumpida caminos.

$11$ falla, ya que $q=5$ no está en la lista. $19$ $q=3*3$ , tanto en la lista, pero vemos por la regla de la potencia, que si $3^2 \mid n$,$3^2 \mid 2^1 +1$, lo cual no es cierto. $17$ $41$ rendimiento incluso $q=4, q=10$. $67$ rendimientos $33 = 3* 11$, pero vemos que la $11$ implica $5$. $43$ rendimientos $7$, no en la lista.

Más grande de los números primos tienen un período de más de 10, por lo que estos $p$ no se puede dividir, porque $q$ ha sido desestimado.

No hay ningún camino de descenso, por lo $3$ es el único ejemplo.