Seja
um inteiro positivo e pofator encontrado pelo algoritmo acha-fator. Se c é o cofator de p como divisor de n, mostre que o menor fator que c pode ter é
.
Passo 1
Beleza, vamos recapitular o que a questão tá pedindo. A gente tem um inteiro positivo
e um algoritmo “acha-fator” que retorna um divisor
de
. Depois, definimos o cofator
como
O que precisamos provar é que o menor fator não trivial de
não pode ser menor que
(em outras palavras, todo divisor de
que seja maior que 1 é pelo menos
).
Matéria envolvida:
- Noções básicas de divisibilidade e cofatores.
- Como funciona o algoritmo acha-fator (ele devolve o menor divisor de
maior que 1). - Prova por contradição (se você assumir o contrário e daí chegar num absurdo).
Passo 2
Antes de tudo, lembra do que é divisor e cofator:
- Dizemos que
é divisor de se existe um inteiro tal que . - Se
divide , então é chamado de cofator de em . - O algoritmo acha-fator faz algo bem simples: testa
até encontrar o primeiro que divida . Logo, é o menor divisor de maior que 1.
Passo 3
Agora vem a ideia principal: prova por contradição.
- Suponha, para chegar a um absurdo, que exista um divisor
de tal que - Como
divide e , temos Isso mostra que também divide (bastou multiplicar ambos os lados por ). - Mas isso contradiz o fato de que o algoritmo acha-fator retorna o menor divisor de
maior que 1. Se realmente dividisse e , o algoritmo teria encontrado antes de !
Passo 4
Como essa situação leva a uma contradição, a suposição de que existe um divisor
de
com
não pode se manter. Logo, todo divisor não trivial de
deve obedecer
.
Resposta
O menor fator que o cofator
pode ter é exatamente
.