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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 10.03.04 00:24, David M. Cardoso at david-obm@suati.com.br 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?
> 
> 
Nao. Tome p = 3  e  n = 6.

O que eh verdade eh que se n eh composto e p eh o menor primo que divide n,
entao p <= sqrt(n).

Pra ver que isso eh verdade, escreva n = p*m.
Se p > m, entao m tem um fator primo menor do que p ==> contradicao.
Logo, p <= m  ==>  p^2 <= p*m = n  ==>  p <= sqrt(n).

[]'s,
Claudio.   



=========================================================================
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
=========================================================================