[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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



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
k<sqrt(n), pois senão teríamos p*k>sqrt(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
=========================================================================