sábado, 9 de junho de 2012

047-Teoremas de Euler e Fermat

No presente post, usarei o conceito de congruências e o teorema de Euler ([;1707-1783;] ) para demonstrar o pequeno teorema de Fermat ([;1601-1665;] ).




Utilizaremos a seguinte notação:

a) "[;|;]" que  significa "divide". Ex:[;a|b;]([;a;] divide [;b;]);
b) [;(a,b);] para indicar o máximo divisor comum de [;a;] e [;b;];
c) [;a \equiv b;]  ( [;mod;] [;m;] ) para indicar que [;a;] e [;b;] deixam o mesmo resto quando divididos por [;m;]. O símbolo [;\equi;] indica uma relação de congruência e suas propriedades estão demonstradas no artigo 048.


Função de Euler : É a função aritmética [; \mathbb{N}\rightarrow \mathbb{N};] definida por

[;\varphi (n)=;] número de inteiros positivos [;\leq n;]que são primos com [;n;]

Por exemplo, no conjunto dos inteiros positivos [; \leq 12;] 

[;\left{1,2,3,4,5,6,7,8,9,10,11,12 \right};] 

verificamos que apenas os elementos [;1,5,7;] e [;11;] são primos com [;12;], logo [;\varphi(12)=4;].

Em particular [;\varphi(1)=1;] e se [;n=p;] for um primo, sabemos que ele é primo com todos os inteiros positivos anteriores ao mesmo. Logo,

[;\varphi(p)=p-1;]

Sistema reduzido de resíduos módulo [;m;] ( s.r.r [;mod;] [;m;] ). É o conjunto [;R_{red(m)};] onde:

Dado o conjunto [;A;] de inteiros positivos [;\leq m;] que são primos com [;m;] [ [;n(A)=\varphi(m);] ],

1) O número de elementos de [;R_{red(m)};] é o mesmo de [;A;];

2) Para cada elemento [;r;] de [;R;] temos um elemento [;a;] de [;A;], onde [;r \equiv a;] ( [;mod;] [;m;] ).

Assim, o próprio conjunto [;A;] pode ser considerado trivialmente um s.r.r [;mod;] [;m;].

Obs: Um sistema completo de resíduos módulo [;m;] ( s.c.r [;mod;] [;m;] ) é aquele onde verifica-se [;1);] e [;2);] mas, neste caso, o conjunto [;A;] seria dos restos da divisão de um inteiro qualquer por [;m;], ou seja, [;A=\left{0,1,2,...,m-1};]  e [;n(A)=m;] .

Exemplos de sistemas reduzidos de resíduos módulo [;12;] 

[;\left{1,5,7,11 \right};] 
e
[;\left{7,35,49,77 \right};] 

De fato, os dois conjuntos possuem o mesmo número de elementos e cada elemento do primeiro conjunto é primo com [;m=12;]. Além disso, referente ao segundo conjunto, temos

[;7 \equiv 7;]     ( [;mod;] [;12;] )
[;35 \equiv 11;]  ( [;mod;] [;12;] )
[;49 \equi 1;]    ( [;mod;] [;12;] )
[;77 \equiv 5;]    ( [;mod;] [;12;] )

Pode-se provar que se

[;\left{r_1,r_2,...,r_{\varphi(m)}\right};]

é um sistema reduzido de resíduos módulo [;m;] e se [;(a,m)=1;], então

[;\left{ar_1,ar_2,...,ar_{\varphi(m)}\right};]
 
também é um sistema reduzido de resíduos módulo [;m;].


Teorema de Euler: Seja  [;a;] [;\in \mathbb{Z};] , [;m;] [;\in \mathbb{N};] com  [;(a,m)=1;]. Então

[;a^{\varphi(m)} \equiv 1;] ([;mod;] [;m;]

Demonstração: Lembrem-se que, em congruências, se [;s \equiv t \Rightarrow us \equiv ut;] ( [;mod;] [;m;] ), mas a recíproca é verdadeira ( propriedade do cancelamento ) apenas se [;(u,m)=1;]

Seja [;\left{r_1,r_2,...,r_{\varphi(m)}\right};] e [;\left{ar_1,ar_2,...,ar_{\varphi(m)}\right};] dois sistemas reduzidos de resíduos módulo [;m;].

Assim, para cada [;1 \leq i \leq \varphi(m);] existe um [;1 \leq j \leq \varphi(m);], onde [;r_i \equiv ar_j;] ( [;mod;] [;m;] ) e, consequentemente,

[;ar_1...ar_i...ar_{\varphi (m)} \equiv r_1...r_i...r_{\varphi (m)};] ( [;mod;] [;m;] ) [;\Rightarrow;] 

[;a^{\varphi(m)}r_1...r_i...r_{\varphi(m)} \equiv r_1...r_i...r_{\varphi (m)};] ( [;mod;] [;m;]

E como cada [;r_i;] é primo com [;m;], ou  seja [;(r_i,m)=1;], podemos utilizar a propriedade do cancelamento:

[;a^{\varphi(m)} \equiv 1;] ([;mod;] [;m;] )


Ex:  Sejam [;a=4;]  e [;m=9;]. Vejam que [;(a,m)=(4,9)=1;]. Os inteiros positivos [;\leq m=9;] que são primos com [;m=9;] são [;1,2,4,5,7;]e [;8;]. Assim [;\varphi (m)= \varphi (9)=6;]. Logo,

[;4^6 \equiv 1;] ([;mod;] [;9;] )

De fato, pois [;9 | (4^6-1) \Rightarrow 9 | 4095;]

E também, sendo [;a=9;] e [;m=4;], já que de qualquer forma [;(9,4)=1;], temos [;\varphi(4)=2;]  e

[;9^2 \equiv 1;] ( [;mod;] [;4;] ), ou seja [;4|(9^2-1) \Rightarrow 4|80;]


Teorema de Fermat: 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;])


Demonstração: Primeiramente, caso [;p|n;], temos [;n \equiv 0;] ( [;mod;][;p;]) [;\Rightarrow n^p \equiv 0;] ( [;mod;][;p;]) e pela propriedade transitiva, [;n^p \equiv n;] ( [;mod;][;p;]).  Suponha, então, [;p \not \mid n;]  e somado ao fato de [;p;] ser um primo temos [;(n,p)=1;]. Logo, pelo teorema de Euler 

[;n^{\varphi(p)} \equiv 1;]  ( [;mod;][;p;]) [;\Rightarrow;] 

[;n^{p-1} \equiv 1;] ( [;mod;][;p;]) [;\Rightarrow;] 

[;n.n^{p-1} \equiv n;] ( [;mod;][;p;]) [;\Rightarrow;]

[;n^p \equiv n;]  ( [;mod;][;p;])


Referência Bibliográfica

Teoria dos Números, de Salahoddim Shokranian, Marcus Soares e Hemar Godinho; Editora UNB, 1999.

6 comentários:

  1. Oi! Teixeira! Ando meio enrolado. Esses teoremas são fundamentais na Teoria do Números, e há mais o de Wilson. lembra-se que eu comentei que com P(n;p) se poderia demonstrá-lo? Bom P(n;n)=n!, agora se p é primo vamos considerar P(p-1;p-1)=(p-1)! Agora usando o pequeno teorema de Fermat em cada termo do desenvolvimento de P(p-1;p-1) o teorema de Wilson sai fácil. abçs

    ResponderExcluir
  2. Oi, Tavano!

    Agora entendi o que quis dizer.Muito interessante! Essa correlação de assuntos matemáticos sempre me impressionaram.

    Eu estava preparando o terreno para provar a recíproca do teorema de Wilson. Já escrevi sobre o de Euler e ainda falta o de Lagrange. Utilizarei estes dois teoremas na clássica demonstração do teorema de Wilson. Neste momento, publicarei a sua demonstração.

    Mas já está em acabamento meu post sobre equação de congruência linear. Depois seguirá sobre o teorema de Lagrange e após isso, as demonstrações de Wilson(incluindo a sua).

    Achei aquele post sobre Fórmula Geral sobre Somatório de Potências excelente e fiquei muito grato com sua colaboração. Pretendo colocá-lo no próximo carnaval UBM.

    Abraços!

    ResponderExcluir
    Respostas
    1. Boa noite. Gostaria de saber o que è essa formula geral sobre somatorio de potencias. estou desenvolvendo um trabalho nessa área e fiquei curioso.
      obrigado

      Excluir
  3. Oi, Palo Lucas! Veja o post 031. Agradeceria se fosse um seguidor.

    ResponderExcluir
    Respostas
    1. Valeu Broder!
      Brigaduuuuuuuuuuuuuu.

      Excluir
    2. Grande Aloisio,
      vc conhece o resultado:
      A FUNÇÃO DE EULER É UMA SOMA FINITA
      Estou tentando publicar, mas tá muito dificil.
      Depois eu posto esse resultado.
      Valeu.

      Excluir