정수론 Chapter 7.4 - Möbius Inversion

Page content

이 글의 내용은 성균관대학교 권순학 교수님의 2019년 5월 9일 수업 내용을 재구성한 것입니다.

Möbius function

$$ \mu(x) = \begin{cases} 1 &\text{if } n = 1 \\ 0 &\text{if } p^2 \mid n ;; \text{for some prime p} \\ -1^t &\text{if } n = \prod_i^t p_i \end{cases} $$

Möbius function is multiplicative

증명

$$ (m, n) = 1 $$

case 1. \(m = 1\) or \(n = 1\)

자명하므로 증명은 생략한다.

case 2. \(p^2 \mid m\) or \(p^2 \mid n\)

$$ \mu(mn) = 0 ;; (\because p^2 \mid mn) $$

$$ \mu(m)\mu(n) = 0 ;; (\because p^2 \mid m or p^2 \mid n) $$

case 3

$$ m = \prod_i^s p_i $$

$$ n = \prod_i^t q_i $$

$$ \mu(mn) = (-1)^{s + t} $$

$$ \mu(m)\mu(n) = (-1)^s (-1)^t = (-1)^{s + t} $$

Theorem 7.8: Summation of \(f\) is multiplicative if \(f\) is multiplicative

$$ F(n) = \sum_{d \mid n} {f(d)} $$

증명

$$ (m, n) = 1 $$

$$ F(mn) = \sum_{d \mid mn} {f(d)} $$

$$ d = gh \\ g \mid m, h \mid n $$

$$ F(mn) = \sum_{d \mid mn} {f(d)} = \sum_{g \mid m} {\sum_{h \mid n} f(d)} \\ = \sum_{g \mid m} {\sum_{h \mid n} f(g)f(h)} \\ = \sum_{g \mid m} {f(g)} \sum_{h \mid n} {f(h)} \\ = F(m) F(n) $$

Theorem 7.15: Summation of Möbius function

$$ \sum_{d \mid n} \mu(n) = \begin{cases} 1 &\text{if } n = 1 \\ 0 &\text{if } n > 1 \end{cases} $$

증명

$$ F(p^a) = \sum_{d \mid p^a} {\mu(d)} \\ = \mu(1) + \mu(p) + \cdots + \mu(p^a) \\ = 1 + -1 \\ = 0 $$

$$ F: \text{multiplicative} \\ \therefore F(n) = 0 ;; \text{ if } n > 1 $$