정수론 Chapter 7.4 - Möbius Inversion
이 글의 내용은 성균관대학교 권순학 교수님의 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 $$