Problema 43 Encontre o MDC de 2^100-1 e 2^120-1.

Passo 1

O enunciado pede o máximo divisor comum de 2^100-1 e 2^120-1. Este é um problema de teoria dos números, envolvendo propriedades de divisibilidade de potências. Para resolver vamos usar a fórmula geral para gcd(a^m-1,a^n-1).

Passo 2

Propriedade: para inteiro a>1 e inteiros positivos m,n, vale
gcdl(a^m-1,;a^n-1r) = a^gcd(m,n) - 1
Este resultado decorre do algoritmo de Euclides aplicado às expressões a^n-1 e a^m-1, reduzindo repetidamente o expoente até gcd(m,n).

Passo 3

Calculamos agora gcd(100,120) pelo algoritmo de Euclides. Como 120 = 100cdot1 + 20, temos
gcd(120,100) = gcd(100,20)
Em seguida, 100 = 20cdot5 + 0, logo
gcd(100,20) = 20

Passo 4

Aplicando a propriedade com a=2, m=100 e n=120, obtemos
gcdl(2^100-1,;2^120-1r) = 2^20-1

Passo 5

Finalmente, calculamos 2^20. Sabemos que
2^10 = 1024 e 2^20 = (2^10)^2 = 1024^2 = 1048576,
portanto
2^20-1 = 1048576 - 1 = 1048575

Resposta

O máximo divisor comum de 2^100-1 e 2^120-1 é 1048575.

Exercícios relacionados