뫼비우스 함수Permalink

Definition 6.3Permalink

양의 정수 $n$에 대해 $\mu(n)$를 다음과 같이 정의한다.

쉽게 풀어말하면, $\mu(1)=1$ 이고, 제곱인수가 있는 수는 $0$이고, 그렇지 않으면 소인수의 개수가 홀수이면 $-1$, 짝수이면 $1$ 인 함수이다.

$\mu(1)=1$ 인 것에서 눈치챘겠지만, 승법 함수이다.

$p$ 가 소수라면

• $\mu(p)=-1$
• $\mu(p^k)=0 ~~ (k \ge 2)$

이다.

이 뫼비우스 함수는 정수론 고인물 문제로 갈수록 가끔씩 튀어나와서 사람들을 괴롭히는데, 이와 관련해서 PS를 위한 정수론 챕터를 만들 때 같이 수록할 예정이다.

Theorem 6.5Permalink

함수 $\mu$는 승법 함수이다.

증명

$m$과 $n$이 서로소일 때, $m$이나 $n$중에 제곱인수가 있는 수가 있다고 해보자.

$p^2 \mid m$ 또는 $p^2 \mid n$ 이면 $p^2 \mid mn$ 이다.

따라서 $\mu(mn)=0=\mu(m)\mu(n)$. 그러면 공식은 성립한다.

이제 $m$과 $n$이 제곱인수가 없다고 하자.

따라서 $\mu$는 승법 함수다. $\square$

정수 $n$의 모든 약수의 뫼비우스 함수값 합Permalink

정수 $n$의 $\sum_{d \mid n}$ 들에 대해서 뫼비우스의 값 합인 $\sum_{d \mid n} \mu(d)$ 가 가지는 놀라운 성질을 알아보자.

$n=1$

$\sum_{d \mid 1} \mu(d)=\mu(1)=1$

$n$은 소수의 거듭제곱

$p$가 소수이고 $n=p^k$ 이라고 하자.

그럼 $n$의 약수는 $\{1,p,p^2,\dots\}$ 이다.

$\sum_{d \mid n}d=\mu(1)+\mu(p)+\mu(p^2)+\cdots=1+(-1)+0+0+\cdots$ 가 되어서 결국 $0$ 이다.

그 외

이전 단원의 Theorem으로 $F(n)=\displaystyle \sum_{d \mid n}\mu(d)$ 일 때, $F$ 도 승법함수이므로,

$n=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$ 이라 한다면, $F(n)=F(p_1^{k_1})F(p_2^{k_2})\cdots F(p_r^{k_r})$ 이 되고,

$F(p_i^{k_i})=0$ 임을 이전에 보였으므로 결국 $F(n)=0$ 이다.

결론적으로, $n=1$ 일 때 빼고는 모두 $\displaystyle \sum_{d \mid n}\mu(d)=0$ 이라는 결론이 나온다.

Theorem 6.6Permalink

양의 정수 $n \ge 1$에 대해,

뫼비우스 반전공식Permalink

Theorem 6.7 뫼비우스 반전공식Permalink

$F$와 $f$를 다음 공식처럼 구성된 수론 함수라 하자.

그러면,

증명

정리의 결론에서, $\displaystyle \sum_{d \mid n}\mu(d)F \left( \dfrac nd \right)=\sum_{d \mid n}\mu \left( \dfrac nd \right)F(d)$ 이 성립하는 이유는, $d'$를, $d'=\dfrac nd$ 로 바꾸어도 성립하기 때문이다.

요구된 계산을 진행하자.

$F(n)=\sum_{d \mid n}f(d)$ 를 그대로 쓴 것이다.

여기서 $d \mid n$이고, $c \mid n/d$ 일 필요충분조건은 $c \mid n$이고, $d \mid n/c$ 임을 보일 수 있다.

$n = dk$라 두면, $c \mid k$ 가 되는데, $k=cx$ 라 하면, $cx \mid k, k \mid n \to c \mid n$ 이고 $\dfrac nc=dx$ 여서 $d \mid \dfrac nc$ 이다.

역방향으로도 동일하다. $d$와 $c$만 바뀐 식이란 것을 관찰할 수 있다. 이것의 예시는 밑에 정리되어있다.

이로써 식을 다시 표현하면

Theorem 6.6에 따라 $\displaystyle \sum_{d \mid n/c} \mu(d)$는 $\dfrac nc=1$ 일 때를 제외하고는 $0$이기 때문에,

즉, $f(n)=\displaystyle \sum_{d \mid n}\mu(d)F \Bigl(\dfrac nd \Bigr) ~~ \blacksquare$

$\sum_{d \mid n}\mu(d)$ 의 성질을 활용하는 방법이 PS에서도 시간복잡도를 줄이는데 많이 쓰인다.

예시

증명 중간에 필요충분조건을 이용해 공식을 변환하는 부분만 예시로 다시 보자.

연산을 이렇게 변환시킬 수 있다는 것을 이해하는 것도 중요하다.

승법 함수와 뫼비우스 반전공식Permalink

$\tau$ 함수와 $\sigma$ 함수를 생각해보자.

Theorem 6.8Permalink

$F$가 승법함수이고, $F(n)=\displaystyle \sum_{d \mid n}f(d)$ 이면, $f$또한 승법함수이다.

증명

$m$과 $n$을 서로소인 양의 정수라 하자.

$mn$의 모든 약수 $d$는 $d_1 \mid m, ~ d_2 \mid n$ 그리고, $gcd(d_1,d_2)=1$ 인 $d=d_1d_2$ 로 유일히 나타낼 수 있다.

뫼비우스 반전공식을 적용하면,

따라서 $f$도 승법적이다. $\square$