quarta-feira, 15 de agosto de 2012

063-A Função de Euler

Seja [;n \in \left{1,2,...,n,... \right};]. Chama-se função de Euler, indicador de [;n;] ou totalizador de [;n;], a função assim definida:

[;\varphi(n)=;] número de inteiros positivos menores ou iguais à [;n;] e que são primos com [;n;].

Ou seja, [;\varphi(n);] é o número de elementos do conjunto

[;\varphi = \left{ x \in \mathbb{N} \ | \ 1\leq x \leq n \ | \ mdc(x,n)=1 \right};]

 Também representa-se esta função por [;\phi(n);]. Eis seus primeiros valores:

[;\varphi(1)=1;]  porque o único inteiro positivo menor que [;1;] é o próprio [;1;]  e ainda se verifica [;mdc(1,1)=1;]. Agora, para qualquer [;n \geq 2;], temos [;n=mdc(n,n) \neq 1;], de forma que, a princípio, [;\varphi(n) \ < \ n;].

Exemplo. Calcular [;\varphi(9);]. Veja que o número de elementos do conjunto

[;\left{ x \in \mathbb{N} \ | \ 1 \leq x \leq 9 \ | \ mdc(x,9)=1 \right}=\left{1, \ 2, \ 4,\ 5, \ 7, \ 8 \right};]

é [;6;] . Logo, [;\varphi(9)=6;]

Este processo de montar o conjunto [;\varphi;] para um certo [;n;] e contar seu número de elementos é fácil apenas se este [;n;] for relativamente pequeno. Esta tarefa torna-se complicada com, por exemplo [;n=12960;].

Mas se [;n;] for primo, simplesmente [;\varphi(n)=n-1;], tendo em vista que todos os inteiros positivos menores que [;n;] primo são primos com o mesmo. Vejam na tabela que [;\varphi(2)=1;], [;\varphi(3)=2;], [;\varphi(5)=4;], [;\varphi(7)=6;] e podem ter certeza que [;\varphi(11)=10;], etc.

Esta é a pergunta principal. Sendo [;n;] um inteiro positivo qualquer, como calcular [;\varphi(n);]? Podemos utilizar, então, a importante propriedade de que a função de Euler é uma função aritmética multiplicatica, ou seja, se [;a;] e [;b;] são inteiros positivos tais que [;mdc(a,b)=1;], então

[;\varphi(ab)=\varphi(a).\varphi(b);] 

Este fato não é evidente e precisa ser demonstrado. Para isto, nos apoiaremos no seguinte teorema auxiliar.

Lema [;1;]. Dados os inteiros positivos [;k;], [;a;] e [;b;], com [;mdc(a,b)=1;], então os restos das divisões dos [;a;] inteiros

[;k;] , [;k+b;], [;k+2b;],...,[;k+(a-1)b;]

por [;a;], são todos diferentes.

Demonstração. Seja a desigualdade [;0 \leq s,t \ < \ a;]. Suponhamos, por absurdo, que [;k+sb;] e [;k+tb;] deixem o mesmo resto na divisão por [;a;].  Assim, [;k+sb=aq+r;] e [;k+tb=aq^'+r;]. Vejam, então, que [;a;] divide o produto [;(s-t)b;]:

[;(k+sb)-(k+tb)=(aq+r)-(aq^'+r) \Rightarrow (s-t)b=a(q-q^') \Rightarrow q-q^'=\frac{(s-t)b}{a};] 

Mas por hipótese, [;mdc(a,b)=1;], logo, [;a;] divide [;(s-t);], o que é impossível porque foi imposto que [;0 \leq s,t \ < \ a;].

Concluimos, então, que os restos, conforme o lema [;1;], são todos diferentes.

Corolário. Como [;a;]  divide com resto [;0\leq r \ < \ a;]   exatamente uma quantidade [;a;] de inteiros positivos, segue que estes restos dispostos em ordem são

[;0;],[;1;],[;2;],...,[;a-1;]


Teorema [;1;]. A função de Euler é uma função aritmética multiplicativa.

Demonstração. O que queremos provar é que  [;\varphi(ab)=\varphi(a).\varphi(b);], desde que [;mdc(a,b)=1;].

Se [;a=1;] ou [;b=1;], o teorema é válido, pois

[;\varphi(1.b)=\varphi(b)=1.\varphi(b)=\varphi(a).\varphi(b);] 

[;\varphi(a.1)=\varphi(a)=\varphi(a).1=\varphi(a).\varphi(b);] 

Sejam, então [;a \ > \ 1;]  e [;b \ > \ 1;] . Vamos agora dispor todos os inteiros [;1;],[;2;],...,[;ab;] em [;a;] linhas e [;b;] colunas, para daí tirar algumas conclusões.


Os inteiros da [;k;]-ésima coluna serão primos com [;b;] apenas se [;k;] for primo com [;b;]. De fato, pois, de modo inverso, [;b;]  divide [;qb+k;] , apenas se [;k;] for múltiplo de [;b;].

Na primeira linha temos [;\varphi(b);] inteiros que são primos com [;b;]. Assim, temos [;\varphi(b);] colunas onde todos os inteiros são primos com [;b;] .

Suponhamos que a [;k;]-ésima coluna seja uma destas [;\varphi(b);] colunas. Pelo lema [;1;], os restos das divisões dos [;a;] inteiros desta coluna por [;a;] são [;1;],[;2;],...,[;a-1;]. Logo, o número de inteiros da [;k;]-ésima coluna que são primos com [;a;] é [;\varphi(a);].

Portando, em cada coluna ( em um total de [;\varphi(b);] ) de inteiros onde todos são primos com [;b;], vamos ter [;\varphi(a);] inteiros que são primos com [;a;].

Logo, o número de inteiros da matriz [;a \ X \ b;] que são primos com [;a;] e [;b;] é [;\varphi(a).\varphi(b);] . É claro que todo número que não tem fatores primos com [;a;] e [;b;] também não terão com o produto [;ab;]. Assim, [;\varphi(a).\varphi(b);] também é a quantidade de inteiros positivos menores que e primos com [;ab;]. Conclusão: [;\varphi(ab)=\varphi(a)\varphi(b);].

Corolário:  Se os inteiros positivos [;a;],[;b;],[;c;],...,[;z;] são primos entre si, dois a dois, então

[;\varphi(abc...z)=\varphi(a)\varphi(b)\varphi(c)...\varphi(z);]

Demonstração. Esta generalização do teorema [;1;] é uma propriedade comum à todas as funções aritméticas multiplicativas e foi demonstrada no post 011.


Já sabemos que se [;n=p;] é primo, então [;\varphi(p)=p-1;] . Dado [;\alpha \in \mathbb{N};], com [;\alpha \geq 1;], vamos demonstrar agora a fórmula para calcular [;\varphi(p^{\alpha});].  
 
Teorema [;2;] .[;\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1};]

Demonstração. Os inteiros menores que [;p^{\alpha};] e que são primos com [;p^{\alpha};] são, obviamente, aqueles números que não possuem o fator primo [;p;]. Os que possuem são da forma [;p;], [;2p;],...,[;tp;], onde 

[;tp=p^{\alpha};][;\Rightarrow t=p^{\alpha -1};]  

Logo, se [; t;] indica a quantidade de inteiros menores que [;p^{\alpha};]que não são primos com [;p^{\alpha};], então a quantidade de inteiros que são menores que e primos com [;p^{\alpha};]são exatamente [;p^{\alpha}-p^{\alpha-1};]. Assim, [;\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1};].

[;\rightarrow;] Agora, com a propriedade multiplicativa da função de Euler em conexão com o teorema [;2;], estamos em condições de calcular [;\varphi (n);] para qualque inteiro positivo [;n;].

Exemplo. Calcular [;\varphi(5625000);].

Primeiro passo. Fatorar [;n=5625000;], ou seja [;n=2^3.3^2.5^7;].

Segundo Passo. Calcular [;\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1};] para cada potência da fatoração.

[;\varphi(2^3)=2^3-2^2=8-4=4;]

[;\varphi(3^2)=3^2-3^1=9-3=6;]

[;\varphi(5^7)=5^7-5^6=78125-15625=62500;]

Terceiro Passo: Aplica-se a propriedade multiplicativa de [;\varphi(n);].

[;\varphi(5625000)=\varphi(2^3.3^2.5^7)=\varphi(2^3).\varphi(3^2).\varphi(5^7)=4.6.62500=1500000;]

Ou seja, existem [;1500000;] inteiros positivos que são menores que e primos com [;5625000;].


Referência bibliográfica 


Edgard de Alencar Filho, Editora Nobel, 1988 


Gostará de ler também:



3 comentários:

  1. ola Aloisio,
    Vc conhece a soma de Paulo?

    phi(n) = soma finita.

    depois mando pra vc

    ResponderExcluir
  2. Não conheço, caro Anônimo.

    Vc é o Paulo?

    Se desejar, mande para o meu e-mail.

    Abraços

    ResponderExcluir
    Respostas
    1. Caro aloisio, me mande seu e-mail. Se preferir acesse youtube/phi de euler / ou a função de euler é uma soma finita.

      Excluir