📂정수론

뫼비우스 역 공식 유도

공식 ¹

$f$ 와 $g$ 가 산술 함수고 $\mu$ 는 뫼비우스 함수다. $$f(n) = \sum_{d \mid n} g(d) \iff g(n) = \sum_{d \mid n} f(d) \mu \left( {{ n } \over { d }} \right)$$

설명

뫼비우스 함수는 그 정의만 보았을 땐 부자연스러운 함수로 보이지만, 사실 산술 함수 전체를 관통하는 핵심 공식에 등장하게 된다. 임의의 산술 함수 $g$ 의 급수는 유닛 함수 $u$ 와 컨볼루션 $\ast$ 을 써서 $g*u$ 와 같이 표현할 수 있는데, 마침 $u$ 의 인버스가 $\mu$, 다시 말해 $I = \mu \ast\ u$ 기 때문이다. 전략: $u$ 는 유닛 함수고 $I$ 는 아이덴터티다. 컨볼루션과 산술 함수의 급수관계를 이용하면 쉽게 유도할 수 있다.

유도

$(\Rightarrow)$

$$f(n) = \sum_{d \mid n} g(d) = \sum_{d \mid n} g(d) u \left( {{ n } \over { d }} \right)$$ 을 컨볼루션 곱으로 표현하면 $f = g \ast\ u$ 이다.

뫼비우스 급수: $$I(n) = \sum_{d \mid n } \mu (d) = \sum_{d \mid n } \mu (d) u \left( {{ n } \over { d }} \right)$$

마찬가지로 뫼비우스 급수를 컨볼루션 곱으로 표현하면 $I = \mu \ast\ u$ 이므로 $$\begin{align*} f \ast\ \mu =& (g \ast\ u) \ast\ \mu \\ =& g \ast\ ( u \ast\ \mu ) \\ =& g \ast\ I \\ =& g \end{align*}$$

---

$(\Leftarrow)$

$$\begin{align*} & f \ast\ \mu = g \\ \implies& f \ast\ \mu \ast\ u = g \ast\ u \\ \implies& f \ast\ I = g \ast\ u \\ \implies& f = g \ast\ u \\ \implies& f(n) = \sum_{d \mid n} g(d) u \left( {{ n } \over { d }} \right) = \sum_{d \mid n} g(d) \end{align*}$$

■