# 정수론 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
$$