Questão 04: Mostre que se (m, n)=d então \left(2^{m}-1,2^{n}-1\right)=2^{d}-1.

Passo 1

O enunciado diz que m e n são inteiros positivos tais que \gcd(m,n)=d, e pede para mostrar que
\gcd\bigl(2^{m}-1,\;2^{n}-1\bigr)=2^{d}-1.
O conteúdo aqui é teoria de divisibilidade, máximo divisor comum e ordens em \Bbb Z_p^*.

Passo 2

Como d=\gcd(m,n), existe inteiro k tal que m = d\,k. Usando a fatoração de soma de potências, temos
2^{m}-1 = 2^{d k}-1 = \bigl(2^{d}\bigr)^{k}-1 = \bigl(2^{d}-1\bigr)\sum_{i=0}^{k-1}\bigl(2^{d}\bigr)^{i}.
Logo \;2^{d}-1\mid 2^{m}-1. De modo análogo, escrevendo n=d\ell, obtemos
2^{n}-1 = \bigl(2^{d}\bigr)^{\ell}-1 = \bigl(2^{d}-1\bigr)\sum_{i=0}^{\ell-1}\bigl(2^{d}\bigr)^{i},
e assim \;2^{d}-1\mid 2^{n}-1. Portanto
2^{d}-1 \;\Bigm|\;\gcd\bigl(2^{m}-1,2^{n}-1\bigr).

Passo 3

Seja
g = \gcd\bigl(2^{m}-1,2^{n}-1\bigr).
Cada primo p que divide g satisfaz
2^{m}\equiv1\pmod p \quad\text{e}\quad 2^{n}\equiv1\pmod p.
Seja t a ordem de 2 em \Bbb Z_{p}^{*}. Então t\mid m e t\mid n, logo t\mid d. Daí
2^{d}\equiv1\pmod p \quad\Longrightarrow\quad p\mid\bigl(2^{d}-1\bigr).
Isso vale para todo primo divisor de g, então
g \;\Bigm|\;2^{d}-1.

Passo 4

Juntando os resultados dos passos anteriores, temos
2^{d}-1 \mid g \quad\text{e}\quad g \mid 2^{d}-1,
portanto
g = 2^{d}-1.

Resposta

\gcd\bigl(2^{m}-1,\;2^{n}-1\bigr) \;=\; 2^{d}-1.

Exercícios relacionados