Encontrar todos los números naturales $n$ tal que $2^n$ divide $3^n -1$

Question

Encontrar todos los números naturales $n$ tal que $2^n$ divide $3^n -1$

Creo que las únicas soluciones son $n = 0,1,2,4$, pero no tengo idea sobre cómo demostrarlo.

Traté de escribir $3^n-1$ $1+3+3^2+...+3^{n-1}$ y manipular la suma, pero encontré a mi mismo en el igual de duro problema de encontrar la potencia de dos dividiendo $3^k+1$

Answer 1

Bien $3^n - 1 = (3-1)(1 + 3 + 3^2 + ... + 3^{n-1}) = 2(1 + 3 + 3^2 + ... + 3^{n-1})$

Por lo $2^n|3^n - 1$ si y sólo si $2^{n-1}|(1 + 3 + 3^2 + ... + 3^{n-1})$.

Si $n$ es impar y mayor que uno $(1+3 + 3^2 + .... + 3^{n-1})$ es extraño por lo tanto podemos suponer $n$ es incluso.

Deje $n = 2m$$2^{2m}|3^{2m} - 1=(3^m -1)(3^m+1)$. Por lo $3^m \pm 1$ son ambos inclusive, y sólo uno de ellos es divisible por $4$.

Por lo $2^{2m-1}|3^m \pm 1$$2^{2m-1} \le 3^m \pm 1$.

Pero $2^{2m-1} = \frac 12*4^{m} \le 3^m \pm 1$

Por lo $(\frac 43)^m \le 2 \pm \frac 2{3^m} < 2\frac 23$

Si $m \ge 3$ $(\frac 43)^m \ge 2 \frac {10}{27} > 2 \frac 2{3^3}\ge 2 + \frac 2{3^m}$

Por lo $m < 3$

Así que si $n > 1$$n= 2m; m\le 2$.

Por lo que las soluciones deben ser un subconjunto de a $\{0,1,2,4\}$.

Y ya ha determinado que $\{0,1,2,4\}$ son todas las soluciones.

====

Probablemente, hay una forma más elegante.

Mi primer pensamiento fue FTL que como $\gcd(3, 2^n) = 1$$\phi(2^n) = 2^{n-1}$$3^{2^{n-1}}\equiv 1 \mod 2^n$. Así

Si $3^m \equiv 1 \mod 2^n$ $m$ es un múltiplo de un no-trivial factor de $2^{n-1}$ .yo.e. incluso

pero que en realidad no se me acerque.

Asimismo, $3^n = (2 + 1)^n = 2^n + \sum{n\choose k} 2^k$ $2^n|\sum{n\choose k} 2^k$ parecía que debe yeild algo relevante, pero no pude poner mi dedo en él exactamente.

Del mismo modo $3^n = (4 -1)^n$.

Su suficiente para convencerme de que las respuestas están relacionadas con los poderes de $2$ pero no lo suficiente para probar realmente es.

Answer 2

El resultado es claro para $n = 0$. Para $ n = 1, 2, 3 \ldots$ deje que el mayor poder de $2$ que divide $3^n - 1$$2^{p(n)}$. Si $n$ es extraño, por decir $n = 2m + 1$,$3^n - 1 = (3 - 1)(3^{2m} + 3^{2m - 1} + \cdots + 1)$. La suma tiene un número impar de términos, por lo $p(n) = 1$. Si $n$ es incluso, decir $n = 2m$,$3^n - 1 = (3^m - 1)(3^m + 1)$. Por inducción, $3^m \equiv 1 \mod 8$ si $m$ es incluso y $3^m \equiv 3 \mod 8$ si $m$ es impar. Por lo tanto $p(2m) = p(m) + 1$ si $m$ es incluso, $p(m) + 2$ si m es impar. Mediante la aplicación de este repetidamente obtenemos que si $n = 2^ab$ donde $a > 0$ $b$ es impar, entonces $p(n) = a + 2$. De ello se deduce fácilmente que para $n > 0$ tenemos $p(n) \ge n$ fib $n = 1, 2, 4$.

Answer 3

Deje $\nu_2(n)=\max\{m\in\mathbb{N}: 2^m\mid n\}$. Podemos abordar el problema dado por la búsqueda de una forma explícita (o, al menos, una explícita algoritmo recursivo para la determinación de la) $\nu_2(3^n-1)$. Dejando $a_n=3^n-1$ hemos $$ a_{2k+1} = 3\cdot 9^k-1\equiv 2\pmod{8}$$ a partir de que $\nu_2(a_{2k+1})=1$, y $$ a_{2k} = a_k (3^k+1) $$ a partir de que $\nu_2(a_{2k})=\nu_2(a_k)+\nu_2(3^k+1)$. En el otro lado $$ 3^{2m+1}+1 = 3\cdot 9^m+1 \equiv 4\pmod{8} $$ $$ 3^{2m}+1 = 9^m+1\equiv 2\pmod{8} $$ por lo $\nu_2(3^{2m+1}+1)=2$$\nu_2(3^{2m}+1)=1$. En particular $$ \nu_2(a_n) \leq 1+2\log_2(n) $$ y las únicas soluciones de $2^n\mid (3^n-1)$ están asociados a $n\leq 7$, por lo que se puede encontrar por inspección directa. En términos explícitos, $$ \nu_2(a_n) = 2+\nu_2(n)-\mathbb{1}_{\text{odd}}(n).$$

Answer 4

Escribo esto con dos ad-hoc inventado notaciones:

• definir $[n:m]=1$ si $m|n \qquad$ $[n:m]=0$ si $m\not |n \qquad$ ("Iverson-soportes")
• definir $\{n,m\} = A $ si $n$ contiene $m$ a la potencia de $A$ o "$n=x \cdot m^A$" (o "valoración" $v_m(n)$)

La evaluación de Fermat poco y teorema de Euler totient teorema y el concepto de "orden cíclico de los subgrupos modulo primer" podemos encontrar: $$ A=\{3^n -1,2\} = 1 + [n:2] + \{ n:2 \} $$ lo que significa también, que el $A$ es logarítmica en $n$ y el número de soluciones debe ser finito y se producen en las pequeñas $A$$n$. Enumeración de los casos pequeños da $$ \begin{array}{rr|l} n & 3^n-1 & A & (=1+ [n:2] + \{n,2\} ) \\ \hline 0 & 0 & \;^\dagger & \;^\dagger \\ 1 & 2 & 1 & 1 + 0 + 0 \\ 2 & 8 & 3 & 1 + 1 + 1 \\ 3 & 26 & 1 & 1 + 0 + 0 \\ 4 & 80 & 4 & 1 + 1 + 2 \\ 5 & 242 & 1 & 1 + 0 + 0 \\ 6 & 728 & 3 & 1 + 1 + 1 \\ \vdots \\ \end{array}$$ ( $\;^\dagger$: esto no es definido aquí y podría ser asumido cero o infinito)
De$n=5$, el menor aumento en $A$ que el de la $n$ entra en la cuenta y por lo tanto no hay más igualdad de $A=n$ puede ocurrir.

(Para obtener más explicite discusión ver un breve texto de la mina)