sábado, 23 de junho de 2012

051-Teorema de Wilson-II

"Se vi mais longe é porque me sustentei sobre ombros de gigantes" 
Isaac Newton ([;1642-1727;])  

 

Para fechar esta série de Teoria dos Números com aritmética modular (ver post 048), demonstrarei o teorema de Wilson ([;1741-1793;]) e sua recíproca ( no post 027 temos uma demonstração elementar do enunciado direto). Serão úteis os teoremas de Euler ([;1707-1783;]), de Lagrange ([;1736-1813;]) e o da fatoração.

Como uma prova alternativa da recíproca do teorema de Wilson, veremos ainda a demonstração do leitor Tavano, onde o mesmo utiliza a fórmula combinativa [;P(n;t);] do preenchimento de [;n;] elementos tomados [;t;] elementos, junto com o pequeno teorema de Fermat ([;1601-1665;]).


Teorema de Euler. Sejam  [;a;] [;\in \mathbb{Z};] e [;m;] [;\in \mathbb{N};]. Se  [;(a,m)=1;], então [;a^{\varphi(m)} \equiv 1;] ([;mod;] [;m;] ), onde [;\varphi (m);] é a função de Euler. Obs: Se [;m;] for primo, temos [;\varphi(m)=m-1;]

Demonstração: post 047.

Teorema de Lagrange. Seja [;p;] um primo e [;A_nx^n+A_{n-1}x^{n-1}+...A_0 \equiv 0;] ([;mod;] [;p;]) uma equação de congruência polinomial [;mod;] [;p;] de grau [;n;], com [;A_n \not \equiv 0;] ([;mod;] [;p;]). Então esta equação tem, no máximo, [;n;] raízes incongruentes [;mod;] [;p;]

Demonstração: post 050.

Teorema da fatoração.  Se  [;x \equiv a;] ([;mod;] [;m;] ) é raiz de [;P(x) \equiv 0;] ([;mod;] [;m;] ) de grau [;n;], então [;P(x) \equiv (x-a)G(x);] ([;mod;] [;m;] ), onde [;G(x);] é um polinômio inteiro de grau [;n-1;]

Demonstração: post 050.

Pequeno teorema de Fermat. É um caso particular do teorema de Euler. Seja [;p \in \mathbb{N};] um primo. Então para qualquer [;n \in \mathbb{N};], temos que [;p|(n^p-n);], ou seja, [;n^p \equiv n;]  ( [;mod;][;p;]) [;\Leftrightarrow;] [;n^{p-1} \equiv 1;] ( [;mod;][;p;]).

Demonstração: post 047

Fórmula de Tavano. Sejam [;n;] e [;t;] [;\in \mathbb{N};], com [;n \leq t;]. Se [;P(n;t);] = número de sequências de [;t;] termos que, em cada uma delas, haja todos os elementos de um conjunto de [;n;] elementos, então  

 [;P(n;t) = {n \choose 0}n^t-{n \choose 1}(n-1)^t+{n \choose 2}(n-2)^t-...+(-1)^{n-1}{n \choose {n-1}}1^t;]

Demonstração: post 031 


_*_

[;<;] Teorema de Wilson [;>;] 
( enunciado direto ) 

[;\frac{(m-1)!+1}{m};] é um inteiro se, e somente se, [;m;] for primo

ou, seja,

[;(m-1)! \equiv -1;] ([;mod;] [;m;] ) se, e somente se, [;m;] for primo 

 _*_

Demonstração. Será por redução ao absurdo. Suponha [;m;] composto. Então o mesmo tem um divisor [;d;] onde [;1<d<m;]. Assim, [;m \equiv 0;] ([;mod;] [;d;] ).

Mas, se [;a \equiv b;] ([;mod;] [;m;]) e [;m \equi 0;] ([;mod;] [;d;] ) , então [;a \equiv b;] ([;mod;] [;d;] ).

De fato, pois [;m \equi 0;] ([;mod;] [;d;][;\Rightarrow d|m \Rightarrow m=qd \Rightarrow qd|(a-b);][;\Rightarrow q|(a-b);] e [;d|(a-b);].

I) Fazendo, [;a=(m-1)!;]   e [;b=-1;], temos que [;(m-1)! \equiv -1;] ([;mod;] [;d;] ).

II) Como [;1<d<m;], logo [;d;] é um dos fatores de [;(m-1)!;]. Portanto,  temos também que [;(m-1)! \equiv 0;] ([;mod;] [;d;] ).

Comparando os dois resultados

[;(m-1)! \equiv -1;] ([;mod;] [;d;] )

[;(m-1)! \equiv 0;]  ([;mod;] [;d;] )

temos que pela propriedade transitiva

 [;0 \equiv -1;] ([;mod;] [;d;] ) [;\Rightarrow 0+1 \equiv 0;] ([;mod;] [;d;] ) [;\Rightarrow d|1 \Rightarrow d=1;], mas isto é um absurdo, pois, por hipótese, [;1<d<m;].

Logo, [;m;] é primo.


_*_ 

[;<;] Teorema de Wilson [;>;] 
( recíproca ) 

Se [;m;] for primo, então [;(m-1)! \equiv -1;] ([;mod;] [;m;]

_*_ 


Demonstração clássica. Partindo do teorema de Euler 

[;a^{\varphi(m)} \equiv 1;] ([;mod;] [;m;] ), desde que  [;(a,m)=1;]

pensando em [;a=x;] como incógnita e fazendo [;\varphi(m)=m-1;], já que [;m;] é primo, temos a equação de congruência polinomial

[;x^{m-1}-1 \equiv 0;] ([;mod;] [;m;] ), que terá raízes para [;(x,m)=1;]

Esta condição é satisfeita para [;(1,m)=1;], [;(2,m)=1;],[;(3,m)=1;],...,[;(m-1,m)=1;], tendo em vista que [;m;] é primo com todos os inteiros positivos [;<m;].

Assim, as classes de equivalência [;x \equiv 1;] ([;mod;] [;m;] ), [;x \equiv 2;] ([;mod;] [;m;] ),...,[;x \equiv {m-1};]([;mod;] [;m;] ) são raízes da equação  [;x^{m-1}-1 \equiv 0;] ([;mod;] [;m;] ) e observem que todas são incongruentes módulo [;m;], ou seja,

[;1 \not \equiv 2 \not \equiv ...\not \equiv (m-1);] ([;mod;] [;m;] )

Como o grau do polinômio é [;m-1;] e o coeficiente de [;x^{m-1};] é incongruente a [;0;] ([;mod;] [;m;]), ou seja, [;1 \not \equiv 0;] ([;mod;] [;m;]), o teorema de Lagrange nos garante que estas são as únicas raízes incongruentes módulo [;m;] desta equação.

Assim, pelo teorema da fatoração, temos a identidade

[;x^{m-1}-1 \equiv (x-1)(x-2)...[x-(m-1)];] ([;mod;] [;m;] )
Fazendo [;x=0;], temos

[;-1 \equiv (-1)^{m-1}(m-1)!;] ([;mod;] [;m;] )

Mas, ainda pelo teorema de Euler, temos que [;(-1)^{m-1} \equiv 1;] ([;mod;] [;m;] ).

Logo, para [;m;]  primo, [;(m-1)! \equiv -1;] ([;mod;] [;m;] )


Demonstração de Tavano


[;I);] Seja [;k \in \mathbb{N};] . Sabemos que

[;(1-1)^k= {k \choose 0}-{k \choose 1}+{k \choose 2}-...+(-1)^k{k \choose k}=0;] 

e, se [;k;] for par, temos

[;{k \choose 0}-{k \choose 1}+{k \choose 2}-...+(-1)^{k-1}{k \choose k-1}=-(-1)^k{k \choose k}=-1;]

[;II);] O teorema de Wilson é verdadeiro para [;m=2;], pois [;(2-1)! \equiv 1 \equiv -1;] ([;mod;] [;2;] );

[;III);] Suponha, então, [;m>2;] (primo). Na fórmula de Tavano

[;P(n;t) = {n \choose 0}n^t-{n \choose 1}(n-1)^t+{n \choose 2}(n-2)^t-...+(-1)^{n-1}{n \choose {n-1}}1^t;] 

fazendo [;n=t=m-1;], temos que

[;P(m-1;m-1)=(m-1)!;] 

[;IV);] Com essa substituição, e pelo pequeno teorema de Fermat, o fator binomial de cada parcela do segundo membro fica [;(m-1-i)^{m-1}\equiv 1;] ([;mod;] [;m;] ), com ( [;i=0,1,2,...,n-1;] ), haja vista que [;m;] é primo e além disso [;(m-1-i)<m;] . Portanto, se verifica a condição [;m.d.c;][([;m-1-i;]), [;m;]][;=1;]

Assim,

[;(m-1)! \equiv {m-1 \choose 0}-{m-1 \choose 1}+{m-1 \choose 2}-...+(-1)^{m-2}{m-1 \choose m-2};] ([;mod;] [;m;])

E  aplicando [;I);]  no segundo membro,

[;(m-1)! \equiv -(-1)^{m-1}{m-1 \choose m-1};] ([;mod;] [;m;]) [;\Rightarrow;]

[;(m-1)! \equiv -1;] ([;mod;] [;m;])



Referência Bibliográfica 

Teoria dos Números, de Salahoddim Shokranian, Marcus Soares e Hemar Godinho; Editora UNB, 1999;
O que é a Matemática?, de Richard Courant e Herbert Robbins, Editora Ciência Moderna, 2000;
Funções Aritméticas  - Números Notáveis, de Edgard de Alencar Filho, Editora Nobel,1988. 


Imagem ( fonte da montagem ):

http://www.leochristopherson.com/Mathematicians.htm
http://semasbc.com.br/?attachment_id=638

3 comentários:

  1. Oi, Teixeira! Ficou muito bom! e obrigado por postar "minha versão". quando fui apresentado ao teorema de Wilson penei uns seis meses sem conseguir demonstrá-lo, e vê-lo aí no post foi para mim motivo de grande satisfação. abrçs

    ResponderExcluir
  2. Oi! de novo! Só para não perder o costume: veja isto: Seja f(x)=(sen pix)^2 + {sen pi[(x-1)!+1]/x}^2, onde x>0, x é real e x! é definido usando a função gama, então os zeros de f(x) são todos os números primos e só eles? Se encontrarmos um meio de resolver f(x)=0 teríamos uma fórmula para primos? abçs

    ResponderExcluir
  3. Oi, Tavano!

    Eu que agradeço por enriquecer o blog!

    Vou analisar esta sua equação.

    Um abraço!

    ResponderExcluir