Sea $f$ una funcion multiplicativa y $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ un entero positivo entonces $$\sum_{d\mid n} f(d)=(f(1)+f(p_1)+\cdots +f(p_1^{\alpha_1}))\cdots (f(1)+f(p_k)+\cdots+f(p_k^{\alpha_k}))$$

Decimos que una funcion $f:\mathbb{N}\to \mathbb{C}$ es multiplicativa si $$f(mn)=f(m)f(n)$$ cuando $m,n$ son primos relativos. Algunos ejemplos de funciones multiplicativas conocidas son: - La funcion $\varphi$ de Euler. - La funcion $\mu$ de Mobius que se define como $\mu(n)=(-1)^m$ si $n$ tiene exactamente $m$ divisores primos, todos distintos entre si. Y $\mu(n)=0$ si $n$ no es libre de cuadrados. - La funcion $\sigma$ la suma de los divisores de $n$. - La funcion $\tau$ que cuenta el numero de divisores de $n$.

Para cualquier congruencia $k\not\equiv 0\text{ mod }p$ tenemos que $$\frac{1}{k}\equiv (-1)^{k-1}\frac{1}{p}{p\choose k}\text{ mod }p.$$

Sea $p > 3$ un primo. Entonces $$(p-1)!(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1})\equiv 0 \text{ mod } p^2.$$

Si $p$ es un primo entonces tenemos que $$1^n+2^n+\cdots +(p-1)^n$$ es $1$ si $p-1\mid n$ y es $0$ si no. Esto les deberia recordar a la suma de raices de la unidad, porque es lo mismo. Pues modulo $p$ tenemos una raiz primitiva $\omega$ y entonces todas las sumas que vemos ahi son $1+\omega^{n}+\omega^{2n}+\cdots+\omega^{(p-2)n}$.

Cuantos subconjuntos de $\{1,2,\ldots, 1000\}$ tienen una suma divisible entre $3$.