Fórmula de inversão de Möbius
A fórmula de inversão de Möbius, assim denominada em homenagem a August Ferdinand Möbius (Schulpforta, 17 de novembro de 1790 - Leipzig, 26 de setembro de 1868) é resultado de teoria elementar dos números que permite explicitar uma função aritmética em termos de uma outra, definida a partir da primeira, e da função de Möbius. Objetivamente, o resultado diz que se f{displaystyle f} e g{displaystyle g} são duas funções aritméticas tais que
f(n)=∑d|ng(d){displaystyle f(n)=displaystyle sum _{d|n}g(d)}, então vale g(n)=∑d|nμ(n/d)f(d){displaystyle g(n)=displaystyle sum _{d|n}mu (n/d)f(d)}
A demonstração que apresentamos a seguir tem a mesma essência de muitas encontradas nos livros de teoria dos números. No entanto, a modificação introduzida elimina um desconforto causado por uma permuta de somatórios muito comum em tais livros didáticos.
Demonstração |
Dado n∈N{displaystyle nin mathbb {N} }, denotemos por D(n){displaystyle D(n)} o conjunto dos divisores de n{displaystyle n} e para cada d∈D(n){displaystyle din D(n)} seja χd:D(n)→{0,1}{displaystyle chi _{d}:D(n)to {0,1}} a função característica de D(d)⊂D(n){displaystyle D(d)subset D(n)}, ou seja, dado m∈D(n){displaystyle min D(n)} temos χd(m)=1{displaystyle chi _{d}(m)=1}, se m∈D(d){displaystyle min D(d)} e χd(m)=0{displaystyle chi _{d}(m)=0} se m∉D(d){displaystyle mnot in D(d)}. Agora para mostrar que g(n)=∑d|nμ(n/d)f(d){displaystyle g(n)=displaystyle sum _{d|n}mu (n/d)f(d)}, partimos do segundo membro e chegamos no primeiro. De fato, Inicialmente observamos que para cada m∈D(n){displaystyle min D(n)} temos
∑d|nχd(m)μ(n/d)=δmn{displaystyle displaystyle sum _{d|n}chi _{d}(m)mu (n/d)=delta _{mn}}, onde δmn=1{displaystyle delta _{mn}=1}, se m=n{displaystyle m=n} e δmn=0{displaystyle delta _{mn}=0} se m≠n{displaystyle mneq n}. Com efeito, as parcelas que contribuem efetivamente no somatório acima são aquelas para as quais d{displaystyle d} é multiplo de m{displaystyle m}. Assim, podem-se escrever d=mq{displaystyle d=mq}, com 1≤q≤n/m{displaystyle 1leq qleq n/m}. Fazendo n′=nm{displaystyle n'={frac {n}{m}}} e usando o fato que d|n{displaystyle d|n} segue que q|n′{displaystyle q|n'}. Reciprocamente, se q|n′{displaystyle q|n'} então d=mq{displaystyle d=mq} é divisor de n{displaystyle n} e múltiplo de m{displaystyle m}.
Portanto, podemos escrever
∑d|nχd(m)μ(n/d)=∑q|n′μ(n′/q)=δn′1=δmn{displaystyle displaystyle sum _{d|n}chi _{d}(m)mu (n/d)=displaystyle sum _{q|n'}mu (n'/q)=delta _{n'1}=delta _{mn}}. A penúltima igualdade é conhecida e a última segue da definição do delta de Kronecker, lembrando que n′=nm{displaystyle n'={frac {n}{m}}}.
Por fim,
∑d|nμ(n/d)f(d)=∑d|nμ(n/d)∑m|dg(m)=∑d|nμ(n/d)∑m|nχd(m)g(m){displaystyle displaystyle sum _{d|n}mu (n/d)f(d)=displaystyle sum _{d|n}mu (n/d)displaystyle sum _{m|d}g(m)=displaystyle sum _{d|n}mu (n/d)displaystyle sum _{m|n}chi _{d}(m)g(m)}
=∑d|n∑m|nμ(n/d)χd(m)g(m)=∑m|n∑d|nμ(n/d)χd(m)g(m)=∑m|n(∑d|nμ(n/d)χd(m))g(m){displaystyle =displaystyle sum _{d|n}displaystyle sum _{m|n}mu (n/d)chi _{d}(m)g(m)=displaystyle sum _{m|n}displaystyle sum _{d|n}mu (n/d)chi _{d}(m)g(m)=displaystyle sum _{m|n}displaystyle (sum _{d|n}mu (n/d)chi _{d}(m))g(m)}
=∑m|nδmng(m)=g(n){displaystyle =displaystyle sum _{m|n}displaystyle delta _{mn}g(m)=g(n)}. Isso conclui a demonstração.
Também vale notar que podemos reverter o processo e reobter a função f{displaystyle f} a partir de g{displaystyle g}. Nas palavras do autor da referência abaixo, se duas funções aritméticas satisfazem uma das equações dadas no enunciado, então também satisfazem a outra. De fato, assumindo que a segunda equação ocorre e mantendo as notações acima, temos
∑d|ng(d)=∑d|n∑m|dμ(d/m)f(m)=∑d|n∑m|nχd(m)μ(d/m)f(m)=∑m|n(∑d|nχd(m)μ(d/m))f(m){displaystyle displaystyle sum _{d|n}g(d)=displaystyle sum _{d|n}displaystyle sum _{m|d}mu (d/m)f(m)=displaystyle sum _{d|n}displaystyle sum _{m|n}chi _{d}(m)mu (d/m)f(m)=displaystyle sum _{m|n}displaystyle (sum _{d|n}chi _{d}(m)mu (d/m))f(m)}
=∑m|n(∑q|n′μ(q))f(m)=∑m|nδn′1f(m)=∑m|nδmnf(m)=f(n).{displaystyle =displaystyle sum _{m|n}displaystyle (sum _{q|n'}mu (q))f(m)=displaystyle sum _{m|n}delta _{n'1}f(m)=displaystyle sum _{m|n}delta _{mn}f(m)=f(n).}
Referências bibliográficas |
- Santos, J.P.O., Introdução à Teoria dos Números, Matemática Universitária, IMPA.
