Арифметична функція

Арифметична функція ${\displaystyle ~\tau \colon \mathbb {N} \to \mathbb {N} }$ визначається як число додатнних дільників натурального числа ${\displaystyle ~n}$:

${\displaystyle ~\tau (n)=\sum _{d|n}1}$

Якщо ${\displaystyle ~m}$ і ${\displaystyle ~n}$ взаємно прості, то кожен дільник добутку ${\displaystyle ~mn}$ може бути єдиним чином поданий у вигляді добутку дільників ${\displaystyle ~m}$ і ${\displaystyle ~n}$, і навпаки, кожне такий добуток є дільником ${\displaystyle ~mn}$. Звідси випливає, що функція ${\displaystyle ~\tau }$ мультиплікативна:

${\displaystyle ~\tau (mn)=\tau (m)\tau (n)}$

Якщо ${\displaystyle ~n=\prod _{i=1}^{r}p_{i}^{s_{i}}}$ — розклад на прості множники натурального числа ${\displaystyle ~n}$, то зважаючи на мультиплікативність

${\displaystyle ~\tau (n)=\tau (p_{1}^{s_{1}})\tau (p_{2}^{s_{2}})\ldots \tau (p_{r}^{s_{r}})}$

Але додатними дільниками числа ${\displaystyle p_{i}^{s_{i}}}$ є ${\displaystyle ~s_{i}+1}$ чисел ${\displaystyle 1,p_{i},\ldots ,p_{i}^{s_{i}}}$.

Відповідно

${\displaystyle ~\tau (n)=(s_{1}+1)(s_{2}+1)\ldots (s_{r}+1)}$

Функція ${\displaystyle \sigma \colon \mathbb {N} \to \mathbb {N} }$ визначається як сума дільників натурального числа ${\displaystyle ~n}$:

${\displaystyle ~\sigma (n)=\sum _{d|n}d}$

Узагальнюючи функції ${\displaystyle ~\tau (n)}$ і ${\displaystyle ~\sigma (n)}$ для довільного, взагалі кажучи комплексного ${\displaystyle ~k}$ можна визначити ${\displaystyle ~\sigma _{k}(n)}$ — суму ${\displaystyle k}$-их степенів додатних дільників натурального числа ${\displaystyle ~n}$:

${\displaystyle ~\sigma _{k}(n)=\sum _{d|n}d^{k}}$

Використовуючи нотацію Айверсона можна записати

${\displaystyle ~\sigma _{k}(n)=\sum _{d}d^{k}[\,d|n\,]}$

Функція ${\displaystyle ~\sigma _{k}}$ мультиплікативна:

${\displaystyle m\perp n\Rightarrow ~\sigma _{k}(mn)=\sigma _{k}(m)\sigma _{k}(n)}$

Якщо ${\displaystyle ~n=\prod _{i=1}^{r}p_{i}^{s_{i}}}$ — розклад на прості дільники натурального числа ${\displaystyle ~n}$, то

${\displaystyle ~\sigma _{k}(n)=\prod _{i=1}^{r}{\frac {p_{i}^{(s_{i}+1)k}-1}{p_{i}-1}}}$

Функція Ейлера ${\displaystyle \varphi (n)}$, визначається як кількість додатних цілих чисел, що не є більшими за ${\displaystyle ~n}$, і є взаємно простими з ${\displaystyle ~n}$.

Користуючись нотацією Айверсона можна записати:

${\displaystyle \varphi (n)=\sum _{1\leq k\leq n}[k\perp n]}$

Функція Ейлера мультиплікативна:

${\displaystyle m\perp n\Rightarrow ~\varphi (mn)=\varphi (m)\varphi (n)}$

У явному вигляді значення функції Ейлера виражається формулою:

${\displaystyle \varphi (n)=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\dots \left(1-{\frac {1}{p_{r}}}\right)}$

де ${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$ — різні прості дільники ${\displaystyle ~n}$.

Функцію Мебіуса ${\displaystyle ~\mu (n)}$ можна визначити як арифметичну функцію, що задовольняє наступній властивості:

${\displaystyle \sum _{d|n}\mu (d)={\begin{cases}1,&n=1\\0,&n>1\end{cases}}}$

Тобто сума значень функції Мебіуса по всіх дільниках цілого додатного числа ${\displaystyle ~n}$ рівна нулю, якщо ${\displaystyle ~n>1}$, і рівна ${\displaystyle ~1}$, якщо ${\displaystyle ~n=1}$.

Можна показати, що цьому рівнянню задовольняє лише одна функція, і її можна явно задати наступною формулою:

${\displaystyle \mu (n)={\begin{cases}(-1)^{r},&n=p_{1}p_{2}\ldots p_{r}\\0,&p^{2}|n\\1,&n=1\end{cases}}}$

Тут ${\displaystyle p_{i}}$ — різні прості числа ${\displaystyle p}$ — просте число. Інакше кажучи, функція Мебіуса ${\displaystyle \mu (n)}$ рівна ${\displaystyle 0}$, якщо ${\displaystyle n}$ не вільно від квадратів (тобто ділиться на квадрат простого числа), і рівна ${\displaystyle ~\pm 1}$ інакше (плюс або мінус вибирається залежно від парності числа простих дільників ${\displaystyle ~n}$).

Функція Мебіуса є мультиплікативною функцією.