Re: Idéia: MDC e pequenos numeros.

[Jorge Peixoto Morais Neto <JorgePeixoto@xxxxxxxxxxxxx>]

22/12/00 14:14:09, "Eduardo Favarão Botelho" <botelho@ajato.com.br> wrote:

>Caro Marcio,
>
>    tive uma idéia para ajudá-lo... Provar que o mdc é diferente de um é o
>mesmo que provar que eles são divisíveis por algum número. Então, a
>diferença entre eles tb será divisível por este número. Teremos (n+1)^17 -
>n^17. Basta fatorar essa expressão para provar. Mas esse, por hora, é o
>nosso maior problema... alguém dá uma mão?
>

Provar que (n+1)^17 -n^17 nao eh primo para algum natural n nao necessariamente envolve fatoracao. Na verdade, pode-se provar que nao hah 
nenhum polinomio (de qualquer grau) de uma unica variavel e coeficientes inteiros que soh assuma valores primos para uma entrada inteira (entrada eh o 
x em P(x))

Um esboco da prova: seja m um inteiro tal que P(m) eh um primo p (positivo). Desenvolva P(m+hp) (ou o faca soh com polinomios de grau mais baixo, pois 
dah menos trabalho e mostra o que acontece no caso geral) e perceba que o resultado eh p*(um numero inteiro). Pode-se facilmente provar que para h 
suficientemente grande, tal inteiro eh maior do que um, e portanto o resultado tem mais de 2 divisores positivos. Em tempo: h eh inteiro positivo. 

Ps: A existencia de metodos de teste de primalidade muito mais eficientes do que algoritmos de fatoracao eh um fator decisivo nos metodos de 
criptografia mais usados, principalmente em aplicacoes comerciais (ou seja: quase tudo o que envolve criptografia).
PS2: Perceba que hah uma relacao de implicancia, mas nao de equivalencia. Se mdc(6;4)=2, 6-4 realmente eh divisivel por dois; mas 21-17=4 nao indica 
que o mdc daqueles numeros seja 4. O problema, portanto, ainda estah aberto.