Mejor prueba de que $2^{n+2}$ divide $3^m-1$ sólo si $2^{n}$ divide $m$

Question

(He aceptado la respuesta de Carl porque fue el primero, pero robjohn y sirous también dieron respuestas muy buenas).

---

Estoy interesado en la mayor potencia de dos que divide $3^m-1$ para incluso $m \geq 2$ . De hecho, puedo demostrar que esto es exactamente cuatro veces la mayor potencia de dos dividiendo $m$ . Es decir, $2^{n+2}$ divide $3^m-1$ sólo si $2^{n}$ divide $m$ para $n \geq 1$ .

Pero, mi prueba parece demasiado tediosa para un hecho tan bonito. La he escrito más abajo, pero como quiero una prueba mejor, quizá quieras ignorarla. (Mi motivación viene de campos finitos, pero la cuestión parece interesante a pesar de todo).

---

Supongamos que $2^{n+2}$ divide $3^m-1$ . La demostración se realiza en dos pasos. En primer lugar, demostramos que el resultado es válido cuando $m$ es a su vez una potencia de dos. Es decir, $2^{n+2}$ divide $3^{2^{n'}}-1$ sólo si $n \leq n'$ . A continuación, demostramos que para cualquier $m$ tal que $3^m-1$ es divisible por $2^{n+2}$ debemos tener $\gcd(m,2^{n}) = 2^{n}$ .

Para la primera parte, observamos la factorización $$ 3^{2^{n'}} - 1 = (3^{2^{n'-1}} +1) (3^{2^{n'-2}} + 1) \cdots (3^2+1)(3+1)(3-1) \;. $$ (Esto no es más que la factorización del $2^{n'}$ polinomio ciclotómico y no utiliza ninguna propiedad del número 3). Dado que $3^a + 1 = 2 \bmod 4$ para todos incluso $a$ la mayor potencia de dos que lo divide es exactamente $2^{n'+2}$ según sea necesario. (Existen $n'+1$ términos, cada uno par. El único término divisible por $4$ es el término $3+1=4$ .)

Para la segunda parte, observamos que si $2^{n+2}$ divide $3^m-1$ ya que $2^{n+2}$ también divide $3^{2^{n}} - 1$ , $2^{n+2}$ deben dividir su diferencia $3^{\min(2^{n},m)}(3^{|m-2^{n}|}-1)$ . Desde $3^{\min(2^{n},m)}$ es impar, lo que a su vez implica que $3^{|m-2^n|}-1$ es divisible por $2^{n+2}$ . Podemos repetir este procedimiento muchas veces para simular el algoritmo euclidiano en el exponente, demostrando finalmente que $3^{\gcd(m,2^{n})} - 1 $ es divisible por $2^{n+2}$ . Por supuesto, $\gcd(m,2^{n})$ debe ser una potencia de dos, y por lo tanto el argumento anterior implica que $\gcd(m,2^{n}) = 2^{n}$ según sea necesario.

Answer 1

Dado un primo $p$ y entero positivo $k$ define $\nu_p(k)$ para ser el exponente de $p$ en la factorización en primos de $k$ . Queremos demostrar que

$$\nu_2\left(3^n-1\right)=\begin{cases} 1&\mathrm{\ if\ }k\equiv 1\bmod 2\\ 2+\nu_2(n)&\mathrm{otherwise}.\end{cases}$$

Utilizamos la inducción fuerte para simplificar los cálculos:

Si $n$ es impar, entonces $3^n-1\equiv 2\bmod 4$ por lo que la afirmación es cierta. Supongamos que la afirmación no es cierta para todos los pares $n$ y considerar el más pequeño de estos $n=2m$ . Tenemos

$$3^{2m}-1=\left(3^m-1\right)\left(3^m+1\right).$$

Si $m$ es par, entonces $\nu_2(3^m-1)=2+\nu_2(m)$ (por nuestra hipótesis inductiva fuerte) y $3^m+1\equiv 2\bmod 4$ así que $\nu_2(3^m+1)=1$ lo que da

$$\nu_2\left(3^{2m}-1\right)=3+\nu_2(m)$$

como desee. Si $m$ es impar entonces $\nu_2(3^m-1)=1$ y $3^m+1\equiv 4\bmod 8$ Así que

$$\nu_2\left(3^{2m}-1\right)=1+2=3=2+\nu_2(2m),$$

como desee.

Esto no es realmente diferente de tu argumento, es sólo una forma más compacta de expresarlo. Se pueden demostrar resultados similares para cualquier $p>2$ ; la forma más general que queda bien es que si $p$ es un primo impar de modo que $p|a-b$ mientras que $p\nmid a,b$ entonces

$$\nu_p\left(a^n-b^n\right)=\nu_p(a-b)+\nu_p(n).$$

(como menciona user236182, esto se llama Levantar el Exponente).

Answer 2

Para $k\ge0$ e impar $p$ , $$ 3^{p2^k}-1=\left(3^{2^k}-1\right)\overbrace{\left(3^{(p-1)2^k}+3^{(p-2)2^k}+\cdots+1\right)}^\text{$ p $ terms} $$ Para $k\ge2$ , $$ 3^{2^k}-1=\left(3^{2^{k-1}}-1\right)\overbrace{\left(3^{2^{k-1}}+1\right)}^{2\pmod4} $$

Answer 3

Se puede utilizar el teorema binomial; podemos escribir:

$3^m-1=(4-1)^m-1$

Ahora bien, si m es par, entonces $3^m-1=(4-1)^m-1=(2^2)^m+M(m,4)$

Donde M(m, 4) significa un polinomio que tiene factores m y 4:

$M(m, 4)= (^m_1) 4^{m-1}(-1)^1 + . . .(^m_{m-1}) 4^1 (-1)^{m-1}=4mk$ ; $k∈ N$

Ahora debemos tener:

$2^{n+2} | 3^m -1$

O:

$(2^2)(2^n) | (2^2)^m +M(m, 2^2)$

Un divisor común de ambos lados de esta relación es $2^2$ ya que la menor potencia de $4$ en RHS es 1, entonces la relación se puede reducir a:

$2^n | 2^{m-1}+ k m$

$2^n$ divide $2^{m-1}$ si $m-1>n$ Por lo tanto, la condición para mantener la relación es si y sólo si $2^n |C^m_i $ para $i=1$ à $i=m-1$ ou $2^n | m$ .