Re: [obm-l] primo(ex.)

["David Daniel Turchick" <dturchic@xxxxxxxxxxxxxx>]

Gabriel, eu não tenho certeza se entendi direito o problema, mas PELO QUE
ENTENDI, o exercício 1 é provar a recíproca do (pequeno) Teorema de Fermat,
i.e., que se n^a-n for divisível por a para todo natural n, a é primo.
Não farei isso, pois ela é FALSA!
Por exemplo, 2^341-2 é divisível por 341, apesar de 341=11*31 ser composto.
Outro exemplo: 3^91-3 é divisível por 91 é inteiro, porém 91=7*13.
Quem sabe você esteja tentando provar o seguinte: se n^a-n for divisível por
a para todo n natural E SE n^b-n NÃO FOR DIVISÍVEL POR a SEMPRE QUE TIVERMOS
1<b<a NATURAL, então a é primo. (o que é verdade)
Dica: você pode usar o Teorema de Euler (de acordo com o qual, USANDO A
NOSSA HIPÓTESE ADICIONAL, a não pode ser maior que phi(a)+1), e o fato que
phi(a)<=a-1 (existe uma fórmula para a função phi(a):
phi(a)=a*(1-(1/p1))*(1-(1/p2))*(1-(1/pk)), onde os p's são todos os k
fatores primos de a (incluindo a caso a seja primo)).
Por exemplo, no segundo exemplo acima, como
phi(91)=91*(1-(1/7))*(1-(1/13))=6*12=72, o Teorema de Euler nos garante que
3^73-3 é divisível por 91, e a nossa hipótese adicional lá em cima fura.
Obs.: eu basicamente COPIEI o que está feito no livro "Number Theory and Its
History", de Oystein Ore, no início do cap. "The Converse Of Fermat's
Theorem", então se você estiver interessado, e tiver a oportunidade, e
REALMENTE ERA ESSE O PROBLEMA QUE VOCÊ TINHA EM MENTE, quem sabe valha a
pena dar uma olhada. O teorema acima se chama Teorema de Lucas.

David

-----Mensagem original-----
De: gabriel guedes <gabriel@hotlink.com.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Sábado, 9 de Fevereiro de 2002 17:16
Assunto: Re: [obm-l] primo(ex.)


>
>Sim tambem é inteiro!
>
>
>
>
>----- Original Message -----
>From: Prof. Doraci. <doraci@cable.splicenet.com.br>
>To: <obm-l@mat.puc-rio.br>
>Sent: Friday, February 08, 2002 9:46 PM
>Subject: Re: [obm-l] primo(ex.)
>
>
>> E quanto ao k, é inteiro?
>> =====================================================
>> Gabriel escreveu:
>> Ola amigos da lista, peço ajuda no seguinte problema,  (n^a - n)/a = k
>> 1)prove q "a" é primo
>> 2)mostre as formulasq k pode assumir
>> abraços
>> Gabriel(Recife, PE)
>>
>> explicações:
>> com n e a pertencentes aos naturais,
>> e k podendo variar.
>>
>> =========================================================================
>> 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
>> O administrador desta lista é <nicolau@mat.puc-rio.br>
>> =========================================================================
>>
>
>=========================================================================
>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
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================
>




=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================