Prueba $2^b-1$ no divide $2^a + 1$ para $a,b>2$

Question

Estoy tratando de probar $2^b-1$ no divide $2^a + 1$ para $a,b>2$ . ¿Puede alguien dar una pista en la dirección correcta para esto?

Answer 1

Sugerencia

Ahora, dejemos que $a=qb+r$ con $0 \leq r <b$ . Entonces

$$2^a+1=2^a-2^r+2^r+1 $$

Demuestra que $2^b-1 | 2^a-2^r$ y concluir que $2^b-1|2^r+1$ . Ahora demuestre que esto contradice $0 \leq r <b$ .

Answer 2

He aquí un planteamiento muy elemental que conduce naturalmente a una prueba. Los números $2^a+1$ y $2^b-1$ tienen formas muy simples en binario:

$$2^a+1=1\underbrace{0000\ldots 0000}_{a-1\text{ zeroes}}1\;,$$

y

$$2^b-1=\underbrace{1111\ldots 1111}_{b\text{ ones}}\;.$$

Supongamos que $a>b$ ya que, de lo contrario, está claro que $2^b-1\nmid 2^a+1$ e imagina que haces una división larga estándar. La primera $1$ en el cociente pasará por encima del $b$ -a cero en $2^a+1$ , y restarás

$$\underbrace{1111\ldots 1111}_{b\text{ ones}}\underbrace{000\ldots 000}_{a-b\text{ zeroes}}$$

de $2^a+1$ para salir

$$1\underbrace{0000\ldots 0000}_{a-b-1\text{ zeroes}}1\;.\tag{1}$$

El número en $(1)$ tiene la misma forma que $2^a+1$ de hecho, es $2^{a-b}+1$ . Has reducido el problema original a otro del mismo tipo pero con un exponente menor en el dividendo . Como este exponente debe ser un entero no negativo, tienes las tripas de una prueba por inducción sobre ese exponente: si ya sabías que $2^b-a\nmid 2^{a-b}+1$ Y si estuvieras haciendo una prueba por inducción, eso sería parte de tu hipótesis de inducción.

En este caso, lo más sencillo es plantear la inducción en términos de un contraejemplo mínimo: si hay algún $n$ tal que $2^b-1\mid 2^n+1$ , dejemos que $a$ ser el menos tal $n$ . Claramente $a>b$ . Convierte ahora los cálculos anteriores en una forma más algebraica:

$$2^a+1=\left(2^b-1\right)\cdot 2^{a-b}+\left(2^{a-b}+1\right)\;,$$

así que

$$2^{a-b}+1=\left(2^a+1\right)-\left(2^b-1\right)\cdot 2^{a-b}\;.\tag{2}$$

$2^b-1$ divide el lado derecho de $(2)$ Así que $2^b-1\mid 2^{a-b}+1$ . Pero $a-b<a$ contradiciendo la minimidad de $a$ Así que, de hecho, no hay $n$ tal que $2^b-1\mid 2^n+1$ .

Por supuesto, esta es exactamente la prueba sugerida en algunas de las otras respuestas; simplemente estoy señalando una forma en la que podrías descubrirla de forma bastante natural.

Tenga en cuenta que la notación binaria simplemente hace que sea especialmente fácil ver lo que está sucediendo, al menos si lo ha utilizado lo suficiente como para tener alguna sensación de ello. Incluso sin ella, es razonable tratar de dividir $2^a+1$ por $2^b-1$ . Desde $2^a=2^b\cdot2^{a-b}$ está claro que el cociente es mayor que $2^{a-b}$ Podrías intentar eso como una primera aproximación, restando $(2^b-1)\cdot 2^{a-b}$ de $2^a+1$ para ver qué restos quedan:

$$2^a+1-\left(2^b-1\right)\cdot 2^{a-b}=2^{a-b}+1\;,$$

y de nuevo descubrirías que has reducido el problema a uno más pequeño del mismo tipo.

Answer 3

¿Conoces el teorema

$$\gcd(a^n-1,a^m-1)=a^{\gcd(m,n)}-1?$$ Si es así, utilícelo observando que si $2^b-1\mid 2^a+1$ entonces $2^b-1\mid 2^{2a}-1$ Así que $b\mid 2a$ . Consideremos ahora los casos en los que $b\mid a$ o $b=2b_0$ con $b_0\mid a$ .

Answer 4

Una pista. Tenemos $b\lt a$ . Sea $a$ sea el menor número entero para el que se cumple el criterio. Consideremos ahora $2^a+1+2^b-1=2^b(2^{a-b}+1)$ que es divisible por $2^b-1$ . Argumentar por contradicción.

Answer 5

Supongamos lo contrario y dejemos que $a$ sea el número entero no negativo tal que $2^b-1\mid 2^a+1$ para algunos $b>2$ . Si $2^a+1=k(2^b-1)$ con $k\ge 1$ entonces $$2^{a-b}+1 = 2^a+1-2^{a-b}(2^b-1)=(k-2^{a-b})(2^b-1).$$ Si $a\ge b$ Esto demuestra que $2^b-1\mid 2^{a-b}+1$ contradiciendo la minimidad de $a$ . Por lo tanto, $a\le b-1$ . Pero entonces tenemos $$2^b-1=2^{b-1}+2^{b-1}-1\ge 2^{b-1}+3>2^a+1$$ contradictorio $2^b-1\mid 2^a+1$ .

---

Tenga en cuenta que $b=2$ nos permite encontrar $2^2-1=3\mid 9=2^3+1$ o $33=2^5+1$ y así sucesivamente.