Questão 01: Prove que existem infinitos n naturais tais que \left(n, 2^{n}-1\right)>1, encontre menor deles.

Passo 1

O enunciado pede para mostrar que há infinitos naturais n tais que \gcd\bigl(n,2^{n}-1\bigr)>1
e, em seguida, encontrar o menor desses n.
O que vamos usar: definição de \gcd, razão de testar valores pequenos para achar o primeiro exemplo, e depois um argumento de família infinita usando aritmética modular e o Pequeno Teorema de Fermat.

Passo 2

Vamos testar os primeiros n e calcular \gcd(n,2^{n}-1):
- \quad n=1: \gcd(1,2^1-1)=\gcd(1,1)=1
- \quad n=2: \gcd(2,2^2-1)=\gcd(2,3)=1
- \quad n=3: \gcd(3,2^3-1)=\gcd(3,7)=1
- \quad n=4: \gcd(4,2^4-1)=\gcd(4,15)=1
- \quad n=5: \gcd(5,2^5-1)=\gcd(5,31)=1
- \quad n=6: \gcd(6,2^6-1)=\gcd(6,63)=3>1

Passo 3

Do cálculo acima vemos que o menor n com \gcd(n,2^n-1)>1 é n=6,
pois \gcd(6,63)=3.

Passo 4

Para produzir infinitos exemplos, note que 3\mid6. Seja
n_k = 6\cdot2^{k},\quad k=0,1,2,\dots
Então 3\mid n_k. Como n_k é par, 2^{n_k}\equiv1\pmod{3} (já que 2^2\equiv1\pmod3), logo
3\mid 2^{n_k}-1.
Assim 3 divide simultaneamente n_k e 2^{n_k}-1, ou seja
\gcd\bigl(n_k,2^{n_k}-1\bigr)\ge3>1
para todo k. Isso garante infinitos n_k com a propriedade desejada.

Resposta

O menor n com \gcd(n,2^n-1)>1 é 6.
Uma família infinita desses n é dada por
n_k = 6\cdot2^{k},\quad k\ge0,
pois para todo k vale \gcd(n_k,2^{n_k}-1)\ge3>1.

Exercícios relacionados