¿Cuándo $n$ brecha $2^n+1$?

Question

Para que $n$,$n\mid2^n+1$ ?

Mi hipótesis es que la única solución es $n=3^k$, para algún entero positivo $k$.

Answer 1

Por desgracia, su afirmación es falsa.

Usted puede encontrar una lista donde $2^n+1 \equiv 0 \pmod {n}$ aquí.

El más pequeño contraejemplo es $n =171$ como se puede observar en la secuencia.

Hay algunos más comentarios aquí.

Curiosamente, la secuencia es cerrado bajo la multiplicación, por lo que si $x,y$ son parte de la secuencia, a continuación, $xy$ es así, como está demostrado en el papel.

Desde $3$ es parte de la secuencia, se sigue que cada número de la forma $3^n$ va a ser en la secuencia. Así, es cierto que $$2^{3^{n}} +1\equiv 0 \pmod {3^n}$$

Además, se puede demostrar que cada miembro de la secuencia es un múltiplo de a $3$.

Answer 2

Para el interés y la accesibilidad, voy a reproducir un resultado en el documento citado por SCB arriba:

Proposición: Si $p \mid n$$n \mid 2^n{+}1$$pn \mid 2^{pn} {+} 1$.

Prueba:$p > 2$. Set $M = 2^n$, dando $2^{pn} + 1 = (M + 1)(M^{p−1} − M^{p−2} + ... − M + 1)$.

Ahora $n \mid M{+}1$ e lo $M \equiv -1 \bmod p$, por lo que
$\begin{align}M^{p−1} − M^{p−2} + ... − M + 1 &\equiv (−1)^{p−1} − (−1)^{p−2} + ... − (−1) + 1 = p \\ & \equiv 0 \bmod p \end{align}$
de modo que $pn \mid 2^{pn} {+} 1$

Desde $3 \mid 2^3{+}1$, esto también nos da inmediatamente $3^{k} \mid 2^{3^k}{+}1$.

También (por ejemplo) dado que el $171 \mid 2^{171}{+}1$$3^2\cdot 19 = 171$, tendremos $c\mid 2^c{+}1$ cualquier $c=3^a\cdot 19^b$ $a\ge2$

---

Thomas Andrews señala que sólo necesitamos tener $p \mid 2^n{+}1$ (en lugar de $p\mid n$) para el resultado anterior. Esto nos permite directamente en algunos de los poderes de la$3_\mathstrut$ soluciones: por ejemplo, debido a $(n,p)=(9,19)$$9 \mid 2^9{+}1$$19\mid 2^9{+}1$, el resultado se sigue que $9\cdot 19 = 171 \mid 2^{171}{+}1$

Answer 3

De manera más general:

Si $n\mid 2^{n}+1$$d\mid 2^n+1$$nd\mid 2^{nd}+1$.

Esto es debido a que $n$ $d$ son impares, así que si $2^{n}\equiv -1\pmod d$ $(-2)^n\equiv 1\pmod d$ e $$\begin{align}\frac{2^{nd}+1}{2^n+1}&=\frac{1-((-2)^n)^d}{1-(-2)^n} \\ &= 1+(-2)^n+(-2)^{2n}-\cdots +(-2)^{n(d-1)}\\ &\equiv 1+1+1+\cdots 1 \\&= d\equiv 0\pmod{d}.\end{align}$$

Por lo $(2^n+1)d\mid 2^{nd}+1$ y, por tanto,$nd\mid 2^{nd}+1$.

Así que podemos decir que una solución de $n$ es absolutamente primitiva si, para cada uno de los prime $p\mid n$, $2^{n/p}+1$ no es divisible por $\mathrm{lcm}(n/p,p).$

Por ejemplo, $171=3^2\cdot 19$ no es absolutamente primitiva debido a $\mathrm{lcm}(171/19,19)=171\mid 2^{171/19}+1$. Y $3$ no es primitivo desde $\mathrm{lcm}(3/3,3)=3\mid 2^{3/3}+1$.

De hecho, me pregunto si hay absolutamente primitiva $n$ otros de $1$.

Si el primer $p\mid n$ $p\mid 2^n+1$ $2^{n}=( 2^{n/p})^p\equiv 2^{n/p}\pmod p$ y, por lo tanto si $n$ es absolutamente primitiva, a continuación, $\frac{n}{p}$ no puede ser un divisor de a $2^{n/p}+1$ para cualquier divisor primo $p$$n$.

Ahora debido a dos factores primos $p,q$ $n$ si $q^k\mid 2^n+1$$q^k\not \mid 2^{n/p}+1$, entonces debemos tener $q\mid \sum_{i=0}^{p-1} (-2)^{ni/p}$. Pero si $q\mid 2^{n/p}+1$, tendríamos $(-2)^{n/p}\equiv 1\pmod{q}$ e lo $q\mid p$, lo cual no es posible.

Esto significa que, si $n$ es absolutamente primitiva, a continuación, para cada uno de los prime $p\mid n$ no debe ser otro prime $q\mid n$ tal que $q\not\mid 2^{n/p}+1$$q\mid 2^{n}+1$.

Pero si $2^{n/p}+1$ no es divisible por $q$ $2^{n}+1$ es divisible por $p$, $-1$ debe ser un no-trivial $p$th poder, modulo $q$, y por lo tanto $q-1$ debe ser divisible por $p$.

Así que si $p$ es el mayor factor principal de $n$, obtenemos que no $q$ puede existir.

Por lo tanto, para cualquier $n$ $n\mid 2^n+1$ $n=1$ o el más grande de prime $p\mid n$ satisface $\frac{n}{p}\mid 2^{n/p}+1$$p\mid 2^{n/p}+1$.

Answer 4

No es necesario que $n = 3^k$, pero es suficiente.

Mediante el Levantamiento de la Exponente Lema, si $p$ es un primer e $a$ $b$ son números naturales no divisible por $p$, asumiendo $p|a+b$, $$v_p(a^n+b^n)=v_p(a+b) + v_p(n).$$

Poniendo ahora $p=3$, $a=1$ y $b=2$, obtenemos $$3^{n+1} | 2^{3^n}+1.$$