Questão 25 da UFG 2006

O algoritmo de Euclides (divisão euclidiana) diz que todo número N pode ser escrito como N = 8k + r, com 0 \le r < 8. Queremos o resto r de N = 2^{25.964.951} - 1.\n\nComo 8 = 2^3, toda potência 2^n com n \ge 3 é múltipla de 8:\n\n

\n\nPassos:\n\n1. O expoente 25.964.951 é bem maior que 3, então 2^{25.964.951} = 8m, com m = 2^{25.964.948} inteiro.\n2. Logo N = 8m - 1.\n3. O resto não pode ser negativo. Reescrevemos: 8m - 1 = 8(m-1) + 8 - 1 = 8(m-1) + 7.\n4. Assim k = m - 1 e r = 7, que satisfaz 0 \le 7 < 8.\n\nConferência com um caso pequeno: 2^5 - 1 = 31 = 8\cdot 3 + 7, resto 7. Vale o mesmo padrão para qualquer n \ge 3.\n\nAlternativa E.

Pegadinha: A alternativa A engana quem esquece o -1 e vê só que 2^n é múltiplo de 8; também é comum deixar o resto como -1 em vez de somar 8.

Por que as outras alternativas estão erradas

• Aesquece o -1 e considera só a potência 2^n, que é múltipla de 8.
• Bnão há base para esse resto; confunde com o resto de potências de 2 pequenas (como 2^1).
• Cresto sem justificativa, não decorre de 8m-1.
• Dresto sem justificativa; o certo é 8m-1 = 8(m-1)+7.

Assuntos: Divisibilidade, MMC e MDC, Potenciação e radiciação.

Reportar erro na resolução

O que está errado?

Conta ou raciocínio errado Chega em outra resposta Explicação confusa Outro problema

Detalhes (opcional) Não preencha

Enviar Sem cadastro: não guardamos quem enviou.