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\]