Mobius Inversion

$$f(n) = \sum_{d|n} g(d)$$

이라고 하자. 이때 $g(n)$의 값을 구하고 싶다. 이때 적용되는 식이 뫼비우스 역공식이다.

$$g(n)= \sum_{d|n} f(d)\mu(\frac{n}{d})$$

$f$가 곱셈적 함수이고 $f(n) = \sum_{d|n} g(d)$이면 $g$ 역시 곱셈적 함수이다.

• Notation

$[P=k]$ : $P=k$일 때 1 아니면 0

$\epsilon(n)$ : $[n=1]$

$\sum_{d|n} \mu(d) =\epsilon(n)$

$\tau(n)$ : $n$의 약수의 개수

$a \perp b$은 $\gcd(a,b)=1$라는 뜻

 

$$1.\ \ \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i, j)$$

$$\sum_{d=1}^{\min(n,m)} d \sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i, j)=d]$$

$i=dp,\ j=dq$이면

$$\sum_{d=1}^{\min(n,m)} d \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} [\gcd(p,q)=1]$$

$$\epsilon(\gcd(p,q))=[\gcd(p,q)=1]=\sum_{s|\gcd(p,q)} \mu(s) = \sum_{s|p,\ s|q} \mu(s)$$

$$\sum_{d=1}^{\min(n,m)} d \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} \sum_{s|p,\ s|q} \mu(s)$$

$$\sum_{d=1}^{\min(n,m)} d \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} \mu(s)[s|p][s|q]$$

$[s|p][s|q]=1$이면 $[s|p]=[s|q]=1$이므로 $p=s\alpha,\ q=s\beta$

$$\sum_{d=1}^{\min(n,m)} d \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} \mu(s) \sum_{\alpha=1}^{\left[\frac{n}{sd}\right]} \sum_{\beta=1}^{\left[\frac{m}{sd}\right]} 1$$

$$\sum_{d=1}^{\min(n,m)} d \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} \mu(s) \left[\frac{n}{sd}\right] \left[\frac{m}{sd}\right]$$

합을 간단히 만들자.

$$1 \le d \le \min(n,m)$$

$$1 \le s \le \min(\left[\frac{n}{d}\right], \left[\frac{m}{d}\right])$$

$$d \le ds \le \min(n,m)$$

$$1 \le d \le k=ds \le \min(n,m)$$

$d|k$가 성립해야 한다.

$$\sum_{d=1}^{\min(n,m)} \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])}$$

는 다음과 같이 쓸 수 있다.

$$\sum_{k=1}^{\min(n,m)} \sum_{d=1}^{\min(n,m)}$$

$d|k$인 조건과 $1 \le d \le \min(n,m)$으로 인해 아래와 같이 쓰인다.

$$\sum_{k=1}^{\min(n,m)} \sum_{d|k}$$

$$\sum_{k=1}^{\min(n,m)} \left[\frac{n}{k}\right] \left[\frac{m}{k}\right] \sum_{d|k} d\mu(\frac{k}{d})$$

좀 더 간단히 하면

$$n=\sum_{d|n} \phi(d)$$

$$\phi(n) = \sum_{d|n} d\mu(\frac{k}{d})$$

$$\sum_{k=1}^{\min(n,m)} \left[\frac{n}{k}\right] \left[\frac{m}{k}\right] \phi(k)$$

 

$$2.\ \ \sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i, j)$$

$\operatorname{lcm}(i, j) = \frac{ij}{\gcd(i,j)}$ 이므로

$$\sum_{i=1}^{n} \sum_{j=1}^{m} \frac{ij}{\gcd(i,j)}$$

$$\sum_{d=1}^{\min(n,m)} \sum_{i=1}^{n} \sum_{j=1}^{m} \frac{ij}{d}[\gcd(i,j)=d]$$

$i=dp,\ j=dq$라 두자.

$$\sum_{d=1}^{\min(n,m)} \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} dpq [\gcd(p,q)=1]$$

$$\epsilon(\gcd(p,q))=[\gcd(p,q)=1]=\sum_{s|\gcd(p,q)} \mu(s) = \sum_{s|p,\ s|q} \mu(s)$$

$$\sum_{d=1}^{\min(n,m)} \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} dpq \sum_{s|p,\ s|q} \mu(s)$$

$$\sum_{d=1}^{\min(n,m)} \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} dpq \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} \mu(s)[s|p][s|q]$$

$$\sum_{d=1}^{\min(n,m)} d \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} \mu(s) \sum_{p=1}^{\left[\frac{n}{d}\right]} \sum_{q=1}^{\left[\frac{m}{d}\right]} pq[s|p][s|q]$$

$[s|p][s|q]=1$이면 $[s|p]=[s|q]=1$이므로 $p=s\alpha,\ q=s\beta$

$$\sum_{d=1}^{\min(n,m)} d \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} \mu(s) s^{2} \sum_{\alpha=1}^{\left[\frac{n}{sd}\right]} \sum_{\beta=1}^{\left[\frac{m}{sd}\right]} \alpha\beta$$

$$\sum_{d=1}^{\min(n,m)} \sum_{s=1}^{\min(\left[\frac{n}{d}\right],\ \left[\frac{m}{d}\right])} d\mu(s) s^{2} \frac{\left[\frac{n}{sd}\right](\left[\frac{n}{sd}\right]+1)}{2} \frac{\left[\frac{m}{sd}\right](\left[\frac{m}{sd}\right]+1)}{2}$$

합을 간단히 만들면

$$\sum_{k=1}^{\min(n,m)} \frac{\left[\frac{n}{k}\right](\left[\frac{n}{k}\right]+1)}{2} \frac{\left[\frac{m}{k}\right](\left[\frac{m}{k}\right]+1)}{2} \sum_{d|k} k\mu(\frac{k}{d}) \frac{k}{d}$$

$$\sum_{k=1}^{\min(n,m)} \frac{\left[\frac{n}{k}\right](\left[\frac{n}{k}\right]+1)}{2} \frac{\left[\frac{m}{k}\right](\left[\frac{m}{k}\right]+1)}{2} \sum_{d|k} k\mu(d) d$$

 

$$f(n) = \sum_{d|n} n\mu(d) d$$

$$\frac{f(n)}{n^{2}} = \sum_{d|n} \frac{1}{d} \mu(\frac{n}{d})$$

$$h(n) = \frac{f(n)}{n^{2}} = \sum_{d|n} g(d) \mu(\frac{n}{d}) \ \ \ g(n)=\frac{1}{n}$$

$g$가 곱셈적 함수이고 조건을 만족하므로 $h$ 역시 곱셈적 함수이다.

$$g(p^{k})=\sum_{i=0}^{k} h(p^{k})$$

$$g(p^{k})-g(p^{k-1}) = h(p^{k})=\frac{f(p^{k})}{p^{2k}}$$

$$f(p^{k})=p^{k}-p^{k+1}$$

 

$$3.\ \ \sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i, j) |\mu(gcd(x,y))|$$

이것 역시 위와 같은 방식으로 정리하면 다음 식을 얻는다.

$$\sum_{k=1}^{\min(n,m)} \frac{\left[\frac{n}{k}\right](\left[\frac{n}{k}\right]+1)}{2} \frac{\left[\frac{m}{k}\right](\left[\frac{m}{k}\right]+1)}{2} \sum_{d|k} k\mu(\frac{k}{d}) \frac{k}{d}|\mu(d)|$$

$$h(n) = \frac{f(n)}{n^{2}} = \sum_{d|n} g(d) \mu(\frac{n}{d}) \ \ \ g(n)=\frac{|\mu(n)|}{n}$$

$d,\ \mu(d)$가 각각 곱셈적 함수이므로 $g(n)$역시 곱셈적 함수이다. 따라서 $h(n)$ 역시 곱셈적 함수이다.

$$f(p^{k})=p^{k}|\mu(p^{k})|-p^{k+1}|\mu(p^{k-1})|$$

$$k=1,\ \ f(p)=p-p^{2}$$

$$k=2,\ \ f(p^{2})=-p^{3}$$

$$k \ge 3,\ \ f(p^{k})=0$$