Re: [obm-l] Problemas Primos

["Frederico Reis Marques de Brito" <fredericor@xxxxxxxxxxx>]

Os exercícios 1 e 2 devem estar enunciados erroneamente. O 1o por ser falso 
e o 2o pore ser absolutamente óbvio. Para o 3o, sugiro olhar a prova de que 
um número natural que não tem divisor primo <= a sua raiz quadrada é primo( 
que se encontra em qq livro de teoria dos num. ) . A prova do exercício é 
análoga.

Quanto ao 4). Pelo pequeno teorema de FermaT, p^{q-1}==1 ( mod q)   e 
q^{p-1} ==1 ( mod p ). Segue que:
p^{q-1} + q^{p-1} ==p^{q-1}(mod q) ==1 ( mod p )  e, analogamente,
p^{q-1} + q^{p-1}== 1 ( mod q).
, ou seja, p| (p^{q-1} + q^{p-1} ) e  q | (p^{q-1} + q^{p-1})
Como p, q são primos distintos ( portanto coprimos ), decorre que se p| x e 
q| x então p.q | x. Assim:

p^{q-1} + q^{p-1}==1 ( mod p.q ).


>From: "Bruno França dos Reis" <bfreis@gmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] Problemas Primos
>Date: Sun, 23 Apr 2006 20:16:30 -0300
>
>1) Tem certeza desse enunciado?
>O número 97^2 = 9409 > 1000 é inteiro e composto, e NÃO tem um fator primo
>menor que 37; seu menor fator primo é 97.
>
>On 4/22/06, Ricardo Khawge <soziwho@hotmail.com> wrote:
> >
> > Se alguém puder me ajudar nestas questões eu agradeço:
> >
> > 1) Mostrar que todo inteiro composto maior que 1000 tem um fator primo
> > menor
> > que 37.
> >
> > 2) Mostrar que um inteiro da forma 4^(2n+1) nunca é primo.
> >
> > 3) Mostrar que, se p não divide n, para todos  os  primos p menores ou
> > iguais a raiz cúbica de n, então n é primo ou é o produto de dois 
>primos.
> >
> > 4) Sejam p e q primos distintos. Demonstrar: p^(q-1) + q^(p-1) ==1(mod 
>pq)
> >
> > Obrigado
> >
> > _________________________________________________________________
> > COPA 2006: Enfeite o seu MSN Messenger de verde e amarelo!
> > http://copa.br.msn.com/extra/emoticons/
> >
> > 
>=========================================================================
> > 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
> > 
>=========================================================================
> >
>
>
>
>--
>Bruno França dos Reis
>email: bfreis - gmail.com
>gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
>icq: 12626000
>
>e^(pi*i)+1=0


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