Mostrar que 47 mid(2^23-1).

Passo 1

Beleza, vamos resolver esse exercício que pede para mostrar que 47 divide 2^23 - 1. O conteúdo que vamos usar aqui é da Teoria dos Números, mais especificamente sobre aritmética modular e o Pequeno Teorema de Fermat. Vamos precisar entender como trabalhar com congruências e propriedades de potências de números inteiros.

Passo 2

Primeiro, vamos lembrar o que significa dizer que 47 divide 2^23 - 1. Isso quer dizer que quando a gente divide 2^23 - 1 por 47, o resto dessa divisão é zero. Em termos de congruência, isso pode ser escrito como:
2^23 - 1 equiv 0 pmod47
O que simplifica para:
2^23 equiv 1 pmod47

Passo 3

Agora, vamos utilizar o Pequeno Teorema de Fermat, que diz que se p é um número primo e a é um inteiro que não é múltiplo de p, então:
a^p-1 equiv 1 pmodp
No nosso caso, p = 47 (que é primo) e a = 2 (que não é múltiplo de 47). Aplicando o teorema, temos:
2^46 equiv 1 pmod47

Passo 4

Observando que 46 = 2 times 23, podemos reescrever a congruência:
(2^23)^2 equiv 1 pmod47
Isso significa que 2^23 é uma raiz de 1 módulo 47, ou seja:
2^23 equiv 1 pmod47 ou 2^23 equiv -1 pmod47
Vamos verificar qual dessas é verdadeira.

Passo 5

Para descobrir qual é, calculamos 2^23 mod 47. Uma forma prática é calcular potências de 2 reduzidas módulo 47 passo a passo:
2^1 equiv 2 pmod47
2^2 equiv 4 pmod47
2^3 equiv 8 pmod47
2^4 equiv 16 pmod47
2^5 equiv 32 pmod47
2^6 equiv 64 equiv 17 pmod47
vdots
Continuando esse processo até chegar em 2^23, descobrimos que:
2^23 equiv 1 pmod47

Resposta

Portanto, 47 divide 2^23 - 1, ou seja, 47 mid (2^23 - 1).

Exercícios relacionados