Функція Мебіуса

Функція Мебіуса $\mu(n)$ — мультиплікативна функція, яку застосовують у теорії чисел і комбінаториці, названа на честь німецького математика Мебіуса, який вперше розглянув її у 1831 р.

Означення

$\mu(n)$ визначена на множині всіх натуральних чисел $n$ і набуває значення ${-1,\;0,\;1}$ в залежності від вигляду розкладу числа $n$ на прості множники:

• $\mu(n)=1$, якщо $n=1$;
• $\mu(n)=0$, якщо $n$ ділиться на квадрат простого числа;
• $\mu(n)=(-1)^k$, якщо канонічний розклад $n$ має вигляд $n=p_1 p_2 ... p_k$, де прості множники різні.

Властивості й застосування

Функція Мебіуса мультиплікативна: для довільних взаємно простих чисел $a$ і $b$ виконується рівність

$\mu(ab)=\mu(a)\mu(b).$

Сума значень функції Мебіуса по всім дільникам цілого числа $n\geq 2$ дорівнює нулю:

$\sum_{d | n} \mu(d) = \left\{\begin{matrix}1,&n=1\\ 0,&n>1\end{matrix}\right.$

Звідси, зокрема, випливає, що для довільної непорожньої скінченної множини кількість різних підмножин, які містять непарне число елементів, дорівнює кількості різних підмножин, які містять парне число елементів — факт, який застосовується у формулі обертання Мебіуса.

Функція Мебіуса пов'язана з функцією Ейлера $\varphi(n)$ таким співвідношенням:

$\varphi(n)=\sum_{d | n} \mu(d) \frac{n}{d},$

де в правій частині перераховуються всі дільники числа $n$.

Обертання Мебіуса

Перша формула обертання Мебіуса

Для арифметичних функцій $f$ і $g$,

$\ g(n) = \sum_{d|n} f(d)$

тоді і тільки тоді, коли

$f(n)=\sum_{d\,\mid\, n}\mu(d)g\left(\frac{n}{d}\right)$.

Цю рівність також називають принципом обертання Дедекінда-Ліувілля на честь німецького математики Ріхарда Дедекінда (1831-1916) та французького математика Жозефа Ліувілля (1809-1882).

Друга формула обертання Мебіуса

Для дійснозначних функцій $f(x)$ і $g(x)$, визначених при $x\geqslant 1$,

$g(x) = \sum_{n\leqslant x} f\left(\frac{x}{n}\right)$

тоді і тільки тоді, коли

$f(x) = \sum_{n\leqslant x}\mu(n) g\left(\frac{x}{n}\right)$.