Re: [obm-l] Pequeno teorema de Fermat

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Thu, Sep 23, 2004 at 06:26:32AM -0700, Artur Costa Steiner wrote:
> Alguem poderia apresentar ou indicar aonde posso
> encontrar a demonstracao deste teorema?

Um monte de gente já respondeu, e alguns já deram a demonstração usando
teoria dos grupos. Uma outra demonstração bem elementar é a seguinte.

Como binom(n,m) = n!/(m! * (n-m)!), segue diretamente do teorema
fundamental da aritmética que, se p é primo, então binom(p,m)
é múltiplo de p para todo 0 < m < p, pois o fator p aparece no numerador
mas não no denominador.

Segue agora do binômio de Newton que para quaisquer inteiros a e b,
(a+b)^p - a^p - b^p = binom(p,1) a b^(p-1) + ... + binom(p,p-1) a^(p-1) b
é múltiplo de p (pois o lado direito o é). Em particular, 
(n+1)^p = n^p + 1 (mod p). Por indução em n temos que n^p = n (mod p)
para todo n.

Uma referência escrita por Gugu e eu é o livro dos primos de Mersenne:

http://www.mat.puc-rio.br/~nicolau/publ/papers/mersenne/index.html

O livro também pode ser comprado via Impa.

[]s, N.
=========================================================================
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
=========================================================================