뫼비우스 함수

Möbius function

Definition. 뫼비우스 함수(Möbius function) \(\mu\)는 수론적 함수(arithmetical function)의 일종으로, 다음과 같이 정의된다.

\[\mu (1)=1\]

어떤 자연수 n>1에 대해 standard prime factorization이 \(n = p_1 ^{a_1} \cdots p_k ^{a_k} \)라면

\[\mu (n) = (-1)^k \; \text{if} \; a_1 = a_2 = \cdots = a_k = 1 \\ \mu (n)=0 \; \text{otherwise} \]

Theroem 1. \(n \in \mathbb{N}\)에 대해 다음이 성립한다.

\[\sum _{d|n} \mu (d) = \left[\frac{1}{n} \right] \]

Proof 1-1. 

\(n = p_1 ^{a_1} \cdots p_k ^{a_k} \)로 놓았을 때 n의 약수 중 뫼비우스 함수가 0이 아닌 것만 고려되므로

n=1일 때 1

n>1일 때는 다음과 같다.

\[\binom{n}{0} + (-1)\binom{n}{1} + \cdots + (-1)^n \binom{n}{n} = (1-1)^n = 0\]

□

Proof 1-2.

소수가 몇 번 곱해지는 지에 관해 귀납적으로 접근하자.

n=1일 때 \(\mu (1) = 1 \), 성립한다.

n=p일 때 \(\mu(p) + \mu(1) = 1-1 = 0 \), 성립한다.

\(n= p_1 ^ {a_1} \cdots p_k ^{a_k} \)로 놓았을 때 \(\sum _{d|n} \mu (d) \)를 N이라고 놓자.

\(p_k+1 \not| n \)일 때 \(np_k+1 = -N \)

\(p_k+1 | n \)일 때 \(np_k+1 = N \)

n=p일 때 \(\sum \mu(d) = 0 \)이므로 \(n = p_1 ^{a_1} \cdots p_k ^{a_k}\)일 때 \(\sum \mu (d) = 0\)이다.

□

Theorem 2. 뫼비우스 함수는 multiplicative function이다.

\[ \mu (a) \mu (b) =\mu (ab) \quad \mathrm{whenever} \; (a,b)=1 \]

a,b 중에 1이 있다면 \(mu(1) =1 \)이므로 명제는 자명하게 성립한다.

a,b 중에 1이 없다면 각각을 standard prime factorization 으로 나타내었을 때 둘 중 하나라도 같은 소수가 2번 나타난다면 그 수를 n으로 놓았을 때 \(\mu (n) =0\)이고, ab도 그 소인수가 2번 곱해져있으므로 \(\mu(ab) =0\)이다. 둘 다 소수가 한 번씩만 나온다면 각 소수의 수를 p,q로 놓자. 그 둘을 곱했을 때 서로소라는 조건에 의해 서로 다른 소수가 p+q번 곱해져 있는 것이다. \[\mu(a) = (-1)^p, \; \mu (b)= (-1)^q, \; \mu (ab) = (-1)^{p+q} \]

역시 곱인 관계가 성립한다. 따라서 theorem은 증명되었다.