Demostrando que $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

Question

En algún lugar de Stack Exchange vi la ecuación

$$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$

Nunca había visto esto antes, así que empecé a intentar probarlo. Sin éxito...

¿Puede alguien explicarme (o sea, demostrar) por qué esta ecuación es cierta?

¿Y se puede decir lo mismo cuando se sustituye el $2$ ' por cualquier número entero ' $a$ '?

Answer 1

En general, si $p=\gcd(m,n)$ entonces $p=mx+ny$ para algunos enteros $x,y$ .

Ahora bien, si $d = \gcd(2^m-1,2^n-1)$ entonces $2^m \equiv 1 \pmod d$ y $2^n \equiv 1\pmod d$ así que $$2^p = 2^{mx+ny} = (2^m)^x(2^n)^y \equiv 1 \pmod d$$

Así que $d\mid 2^p-1$ .

Por otro lado, si $p\mid m$ entonces $2^p-1\mid 2^m-1$ así que $2^p-1$ es un factor común.

Y sí, puedes sustituir $2$ con cualquier $a$ .

Answer 2

Sugerencia $\rm\ \ mod\ d\!:\ 2^a\equiv 1\equiv 2^b\iff order(2)\,|\,a,b\iff order(2)\,|\,(a,b)\iff 2^{(a,b)}\equiv 1$

Por lo tanto, $\rm\ d\,|\,2^a-1,\,2^b-1\:$ $\iff$ $\rm\:d\,|\,2^{(a,b)}-1,\ \,$ por lo que $\rm\, \ (2^a-1,\,2^b-1)\, =\, 2^{(a,b)}-1.$

Answer 3

Sí, se puede decir lo mismo cuando se sustituye $2$ con un número entero $a \geqslant 2$ .

Lema. Supongamos que $a \geqslant 2$ , $m, n \in \mathbb{N}$ y $\gcd(m, n)=1$ . Entonces $\gcd(a^m-1, a^n-1)=a-1$ .

Prueba. Es evidente que $(a-1) | \gcd(a^m-1, a^n-1)$ . Por lo tanto, sólo tenemos que demostrar que $\gcd(a^m-1, a^n-1) | (a-1)$ .

Es bien sabido que si $\gcd(m, n)=1$ entonces existe $k, l \in \mathbb{N}$ tal que $mk-nl=1$ . Si es obvio que $(a^n-1)|(a^{nl}-1)$ Por lo tanto $$ \gcd(a^m-1, a^n-1) | (a^{nl}-1), $$ y por la misma razón $$ \gcd(a^m-1, a^n-1) | (a^{mk}-1). $$

Ahora sólo observamos que $$ (a^{mk}-1)-a\cdot(a^{nl}-1) = (a^{nl+1}-1)-(a^{nl+1}-a) = a - 1, $$ por lo tanto $$ \gcd(a^m-1, a^n-1) | (a-1), $$ QED.

Ahora podemos demostrar la afirmación principal: para $b \geqslant 2$ que tenemos: $$ \gcd(b^m-1, b^n-1) = b^{\gcd(m,n)}-1. $$ Prueba. Establecer $a = b^{\gcd(m, n)}$ , $m'=m/\gcd(m,n)$ y $n'=n/\gcd(m,n)$ . Claramente, $\gcd(m',n')=1$ y por el lema tenemos $$ \gcd(a^{m'}-1,a^{n'}-1) = a-1, $$ que es exactamente lo que necesitamos, QED.

Answer 4

Supongamos que $x$ , $m$ y $n$ son enteros positivos con $m$ y $n$ coprima. Primero demostremos que $$r = 1 + x + {x^2} + \ldots + {x^{m - 1}}$$ y $$s = 1 + x + {x^2} + \ldots + {x^{n - 1}}$$ son relativamente primos. Si $d$ es un divisor común de $r$ y $s$ entonces $d$ es relativamente primo de $x$ porque $r$ y $s$ son uno más que un múltiplo de $x$ . Dejemos que $m$ ser mayor que $n$ (o viceversa) y considerar $$r - s = {x^n} + {x^{n - 1}} + \ldots + {x^{m - 2}} + {x^{m - 1}} = {x^n}(1 + x + \ldots + {x^{m - n - 1}})$$ y observe que $d$ divide $r - s$ y por lo tanto debe ser un divisor de $1 + x + \ldots + {x^{m - n - 1}}$ . Observe que $m - n$ es relativamente primo de ambos $m$ y $n$ por lo que podemos igualmente utilizar sumas geométricas que eventualmente se hacen cada vez más cortas hasta concluir que $d$ debe dividir a 1, es decir $d = 1$ . Ahora bien, si dejamos que $$d' = \gcd (m',n')$$ con $m' = md'$ y $n' = nd'$ entonces $m$ y $n$ son coprimos y $${2^{m'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(m - 1)d'}})$$ $${2^{n'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(n - 1)d'}})$$ que son sumas geométricas con $x = {2^{d'}}$ y demostramos que $\gcd (r,s) = 1$ . Esto completa la prueba.

Answer 5

si (m,n)=p, entonces p|m, y p|n, entonces $m=m_1p$ , $n=n_1p$ , $(m_1,n_1)=1$ entonces $(2^{m_1p}-1,2^{n_1p}-1)=((2^{p})^{m_1}-1,(2^{p})^{n_1}-1)=((2^{p}-1)(.....),(2^{p}-1)(.....))=(2^{p}-1)$