Número de divisores / soma de divisores

Neste artigo, discutiremos como calcular o número de divisores $d(n)$ e a soma dos divisores $\sigma(n)$ de um dado número $n$.

Número de divisores

A fatoração em primos de um divisor $d$ deve ser um subconjunto da fatoração em primos de $n$, e.g. $6 = 2 \cdot 3$ é um divisor de $60 = 2^2 \cdot 3 \cdot 5$. Portanto, precisamos apenas encontrar todos os subconjuntos diferentes da fatoração de $n$.

Normalmente, o número de subconjuntos é $2^x$ para um conjunto com $x$ elementos. No entanto, isso não é mais verdade, se houver elementos repetidos no conjunto. No nosso caso, alguns fatores primos podem aparecer várias vezes na fatoração de $n$.

Se um fator primo $p$ aparecer $e$ vezes na fatoração de $n$, então podemos usar o fator $p$ até $e$ vezes no subconjunto. Significa que temos $e+1$ escolhas.

Portanto, se a fatoração em primos de $n$ for $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$, onde $p_i$ são números primos distintos, então o número de divisores é: $$d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$$

Uma maneira de pensar sobre isso é a seguinte:

Soma de divisores

Podemos usar o mesmo argumento da seção anterior.

Funções Multiplicativas

Uma função multiplicativa é uma função $f(x)$ que satisfaz $$f(a \cdot b) = f(a) \cdot f(b)$$ se $a$ e $b$ são coprimos.

Ambos $d(n)$ e $\sigma(n)$ são funções multiplicativas.

As funções multiplicativas têm uma enorme variedade de propriedades interessantes, que podem ser muito úteis em problemas da teoria dos números. Por exemplo, a convolução de Dirichlet de duas funções multiplicativas também é multiplicativa.

Problemas