2009/4/8 Artur Steiner <[email protected]>: > Eu nao consegui chegar a uma conclusao neste aqui. Talvez haja uma saida > trivial que nao vi. Tentei usar o teorema de Wilson. > > Mostre que o inteiro positivo eh primo se, e somente se, > > (n - 2! = 1 (mod n) Acho que faltou um parênteses, não ? (n-2)! = 1 mod n. Se for isso :
Wilson da uma das direções, se eu não me engano : n primo => (n-1)! = -1 mod n e como (n-1) = -1 mod n temos (n-2)! = -1/-1 = 1 mod n Agora, se n é composto, n = p*q, com p,q >= 2. Logo p e q são menores do que (n-2) (pois n-2 < n/2 <=> n < 4, e tanto p como q são <= n/2), logo p e q dividem (n-2)!. Não se apresse a dizer que n = p*q divide (n-2)!, pois a gente ainda não sabe se eles são primos entre si : se fosse o caso, tudo certo, senão, tem que tirar o mdc ! Mas isso já permite concluir se n tiver mais de um fator primo, o que da bastantes números ! Bom, faltam os números da forma p^k com k inteiro >=2 e p primo, também >= 2. A idéia agora é achar vários caras que são múltiplos de p e menores ou iguais a (n-2), e todos eles vão dividir (n-2)!, e se a gente achar mais do que k, acabou. A idéia é a seguinte : temos p e p^k, queremos achar os múltiplos m de p tais que p <= m <= p^k - 2, ou, o que da na mesma, <= p^k - p. Ou seja, temos 1/p(p^k - p - p) + 1 (lembre de contar as extremidades também !) ou seja, temos p^(k-1) - 1 múltiplos de p entre p e p^k - 2. Ora, queremos pelo menos k deles, ou seja queremos k <= p^(k-1) - 1 e basta k <= 1 + (p-1)(k-1) - 1 = (p-1)(k-1) usando (1+a)^b >= 1 + ab para a,b positivos, b>1. Se p é maior do que 2, temos que basta k <= 2*(k-1) ou seja k >= 2, o que é verdade (pois n não é primo !). Agora, se p for igual a 2, vamos fazer as contas direitinho : k <= 2^(k-1) - 1 = 1 + 2 + 2^2 + ... + 2^(k-2) com exatamente (k-1) termos (é uma soma de PG!). Se k é maior do que 2, temos pelo menos os termos 1 + 2 no inicio, e como cada termo é maior do que 1, e o 2 = 1+1, temos que a soma dos (k-1) termos é realmente maior ou igual a k :) Se, por outro lado, k=2, não da certo. Mas ai, é so verificar o que da a conta para n = 2^2 : (n-2)! = 2! = 2 == 2 mod 4, e como nao é 1 (ufa!!), mesmo esse caso da certo. Resumindo : (n-2)! mod n = 1 se n é primo (n-2)! mod n = 2 se n = 4 (n-2)! mod n = 0 em todos os outros casos ! -- Bernardo Freitas Paulo da Costa ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
