Use congruências para verificar
(a) 89 mid(2^44-1).

Passo 1

Primeiro, vamos entender o que a questão está pedindo. Queremos verificar, usando congruências, se divide . Para isso, vamos utilizar conceitos de aritmética modular e propriedades de congruências.

Passo 2

Sabemos que se queremos verificar se um número 2^44 - 1 equiv 0 mod 89 divide outro número , isso é equivalente a dizer que . No nosso caso, queremos verificar se divide , ou seja, se:

Passo 3

Isso significa que precisamos calcular e ver se o resultado é igual a . Se , então divide .

Passo 4

Para facilitar os cálculos, podemos usar o Pequeno Teorema de Fermat, que afirma que se a^p-1 equiv 1 mod p é primo e não é múltiplo de , então:

Passo 5

Como 2^88 equiv 1 mod 89 é um número primo, segundo Fermat temos:
Isso nos dá uma relação útil para calcular potências de módulo .

Passo 6

Queremos encontrar 2^44 equiv raiz2^88 mod 89 . Observamos que 2^44 equiv pm 1 mod 89 é exatamente metade de , então podemos relacionar isso com a congruência de Fermat:
Sabemos que , então:

Passo 7

Precisamos determinar se ou . Para isso, vamos calcular e depois elevar o resultado à 4ª potência para obter .

Passo 8

Calculamos 2048 div 89 = 23 com resto 2048 - (89 times 23) = 2048 - 2047 = 1 . Agora, dividimos 2048 por 89 para encontrar o resto:
2^11 equiv 1 mod 89
Portanto:

Passo 9

Agora, elevando ambos os lados à 4ª potência:
(2^11)^4 equiv 1^4 mod 89 2^44 equiv 1 mod 89

Resposta

Portanto, divide , já que .

Exercícios relacionados