Seja n 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 é p.

Passo 1

Beleza, vamos recapitular o que a questão tá pedindo. A gente tem um inteiro positivo c = np 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.
  1. Suponha, para chegar a um absurdo, que exista um divisor 1 < q < p de c = q cdot r Longrightarrow np = q ,r Longrightarrow n = p ,(q,r) = (p,q),r tal que
  2. Como divide e , temos Isso mostra que também divide (bastou multiplicar ambos os lados por ).
  3. 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 .

Exercícios relacionados