Re: [obm-l] p < sqrt(n)

[Guilherme Carlos Moreira e Silva <luis_e_rosa@xxxxxxxxxxxx>]

é isto que demonstra que:

n é primo, se ele nao tem divisor menor que ou igual a sqrt(n).

Ricardo Bittencourt <ricbit@700km.com.br> wrote:

David M. Cardoso wrote:
> oi...
>
> É possível dizer que se p é um primo que divide n, então p < sqrt(n), certo?
> Se isso está certo, é fácil demonstrar?

Certo com restrições. Na verdade o que dá pra demostrar
que é existe um primo p < sqrt(n), não que todo primo é menor que
sqrt(n). Esse é o teorema da fatia do bolo. Se você divide um bolo em
duas partes, e as partes não ficam iguais, então uma das partes é maior
que a outra.

Ou seja suponha que n=p*k, onde p é um primo maior que
sqrt(n). Como p*k tem que ser igual a n, e p>sqrt(n), então
ksqrt(n)*sqrt(n)=n>n, que
é uma contradição.

Aqui k não precisa ser primo, mas se for composto,
então os primos que o compõe são ainda menores que ele. Então
vale que sempre tem um primo menor ou igual a sqrt(n) na
decomposição única de n.

----------------------------------------------------------------
Ricardo Bittencourt http://www.mundobizarro.tk
ricbit@700km.com.br "tenki ga ii kara sanpo shimashou"
------ União contra o forward - crie suas proprias piadas ------
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================

---

Yahoo! Mail - 6MB, anti-spam e antivírus gratuito. Crie sua conta agora!