Ache o resto da divisão euclidiana de a por b nos seguintes casos:
a=2^{45} e b=7.

Passo 1

O enunciado dá a=2^{45} e b=7 e pede: encontrar o resto da divisão euclidiana de a por b.
Isto é, encontrar um inteiro r tal que exista um inteiro q com
2^{45}=7q+r
e
0\le r<7.

Passo 2

Vamos traduzir isso em linguagem de congruências (útil para potências grandes). Definição e propriedades básicas que usarei:
  • Dizemos que dois inteiros x e y são congruentes módulo 7 quando x-y é múltiplo de 7. Escreve-se x\equiv y\pmod{7}.
  • O resto da divisão de x por 7 é justamente o representante r com 0\le r<7 tal que x\equiv r\pmod{7}.
  • Propriedade para potências: se x\equiv y\pmod{7} então para todo inteiro k\ge0 vale x^k\equiv y^k\pmod{7}. Isso permite reduzir bases ou expoentes quando possível.

Passo 3

Calculo direto dos primeiros poderes de 2 módulo 7 para ver se há um padrão:
2^1=2\equiv2\pmod{7},
2^2=4\equiv4\pmod{7},
2^3=8\equiv1\pmod{7}.
Como \,2^3\equiv1\pmod{7}, a sequência de restos repete a cada 3 expoentes. Para ver isso, calcule:
2^4=2^3\cdot2\equiv1\cdot2\equiv2\pmod{7},
2^5\equiv4\pmod{7},\quad 2^6\equiv1\pmod{7},
e assim por diante. Logo o período (ciclo) dos restos de 2^n módulo 7 é 3.

Passo 4

Agora reduzo o expoente 45 módulo o período 3. Dividindo 45 por 3 obtenho
45=3\cdot15.
Portanto
2^{45}=(2^3)^{15}.
Usando 2^3\equiv1\pmod{7} segue
2^{45}=(2^3)^{15}\equiv 1^{15}\equiv1\pmod{7}.
Isto significa que o resto da divisão de 2^{45} por 7 é 1.

Passo 5

Observação pedagógica rápida: poder-se-ia também aplicar o Teorema Pequeno de Fermat que diz que, para primo p=7 e base 2 não múltipla de 7, tem-se 2^{6}\equiv1\pmod{7}. Aqui encontramos um período ainda menor ( 3), o que simplifica o cálculo. Mas o argumento anterior, verificando 2^3\equiv1\pmod{7}, já é suficiente e direto.

Resposta

1

Exercícios relacionados