2.1 산술 함수 & 디리클레 합성 실전 예제 10선
함수 간의 합성($(f * g)(n)$)과 뫼비우스 반전 공식을 통해 복잡한 수론적 합을 단순화하는 기법을 익혀봅니다.
Ex 1. 항등함수 $\epsilon$의 성질
문제: $\epsilon(n) = [n=1]$ 일 때, 모든 산술 함수 $f$에 대해 $f * \epsilon = f$ 임을 보이시오.
$(f * \epsilon)(n) = \sum_{d|n} f(d)\epsilon(n/d)$ 이다.
$\epsilon(n/d)$는 $n/d = 1$, 즉 $d=n$일 때만 1이고 나머지는 0이다.
따라서 합의 기호에서 $d=n$인 항만 남으므로:
$(f * \epsilon)(n) = f(n) \cdot 1 = f(n)$
$\therefore f * \epsilon = f$
Ex 2. 가우스의 정리 ($\phi$의 합)
문제: $\sum_{d|n} \phi(d) = n$ 임을 증명하시오.
$F(n) = \sum_{d|n} \phi(d)$라 하자. $\phi$가 곱셈적 함수이므로 $F$도 곱셈적이다.
$n = p^k$ (소수의 거듭제곱)인 경우만 확인하면 된다.
$F(p^k) = \phi(1) + \phi(p) + \phi(p^2) + \dots + \phi(p^k)$
$= 1 + (p-1) + (p^2-p) + \dots + (p^k - p^{k-1}) = p^k$ (망원급수 형태)
모든 $n = \prod p_i^{e_i}$에 대해 $F(n) = \prod F(p_i^{e_i}) = \prod p_i^{e_i} = n$.
Ex 3. $\mu$ 함수의 핵심 항등식
문제: $n > 1$ 일 때, $\sum_{d|n} \mu(d) = 0$ 임을 증명하시오.
$n = p_1^{a_1} \dots p_k^{a_k}$라 하자. $\mu(d)$가 0이 아닌 경우는 $d$가 서로 다른 소수들의 곱일 때뿐이다.
$\sum_{d|n} \mu(d) = \binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \dots + (-1)^k \binom{k}{k}$
이항정리에 의해 이는 $(1-1)^k = 0$이다.
(단, $n=1$이면 $\mu(1)=1$이다.)
Ex 4. $\tau$ 함수의 디리클레 표현
문제: $I(n)=1$인 상수함수일 때, $\tau = I * I$ 임을 보이시오.
$(I * I)(n) = \sum_{d|n} I(d)I(n/d) = \sum_{d|n} 1 \cdot 1 = \sum_{d|n} 1$
어떤 수 $n$의 약수의 개수만큼 1을 더하는 것이므로 이는 $\tau(n)$의 정의와 일치한다.
$\therefore \tau = I * I$
Ex 5. $\phi$ 함수와 $\mu$의 관계
문제: $\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}$ 임을 유도하시오.
예제 2에서 $\sum_{d|n} \phi(d) = n$임을 보였다.
이를 디리클레 합성으로 쓰면 $n = (\phi * I)(n)$이다.
양변에 $\mu$를 디리클레 합성하면:
$n * \mu = (\phi * I) * \mu = \phi * (I * \mu)$
$I * \mu = \epsilon$ (예제 3의 결과)이므로, $n * \mu = \phi * \epsilon = \phi$.
$\therefore \phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}$
Ex 6. $\sigma$ 함수의 합성 표현
문제: $N(n)=n$인 항등함수일 때, $\sigma = N * I$ 임을 보이시오.
$(N * I)(n) = \sum_{d|n} N(d)I(n/d) = \sum_{d|n} d \cdot 1 = \sum_{d|n} d$
이는 $n$의 모든 약수의 합이므로 $\sigma(n)$의 정의와 같다.
Ex 7. 완전 곱셈적 함수의 역원
문제: $f$가 완전 곱셈적 함수이면 $f^{-1}(n) = \mu(n)f(n)$ 임을 증명하시오.
$(f * (\mu f))(n) = \sum_{d|n} f(d)\mu(n/d)f(n/d)$
$f$가 완전 곱셈적이므로 $f(d)f(n/d) = f(n)$이다.
$= f(n) \sum_{d|n} \mu(n/d) = f(n) \sum_{d|n} \mu(d)$
$n=1$이면 $f(1)\mu(1)=1$, $n>1$이면 $f(n) \cdot 0 = 0$.
이는 $\epsilon(n)$의 정의와 같으므로 $\mu f$는 $f$의 디리클레 역원이다.
Ex 8. $\mu^2$ 함수의 의미
문제: $f(n) = \mu^2(n)$ 일 때, $\sum_{d^2|n} \mu(d)$의 값을 구하시오.
$\mu^2(n)$은 $n$이 제곱인수를 갖지 않으면 1, 갖으면 0이다(Square-free indicator).
정리: $\mu^2(n) = \sum_{d^2|n} \mu(d)$.
이 식은 $n$을 소인수분해하여 각 지수가 2 이상인 경우 $\mu$의 성질에 의해 상쇄됨을 보임으로써 증명 가능하다.
Ex 9. 리우빌 함수와 $\mu$
문제: 리우빌 함수 $\lambda(n) = (-1)^{\Omega(n)}$에 대해 $\sum_{d|n} \lambda(d)$의 값을 구하시오.
$\lambda$는 완전 곱셈적 함수이다. $F = \lambda * I$라 하면 $F$는 곱셈적이다.
$F(p^k) = \sum_{i=0}^k \lambda(p^i) = \sum_{i=0}^k (-1)^i$
이는 $k$가 짝수면 1, 홀수면 0이다.
$\therefore \sum_{d|n} \lambda(d) = 1$ ($n$이 완전제곱수일 때), $0$ (그 외).
Ex 10. $\phi(n)/n$의 평균값 관련 합
문제: $\sum_{d|n} \frac{\mu(d)}{d}$를 $\phi(n)$으로 표현하시오.
예제 5에서 $\phi(n) = n \sum_{d|n} \frac{\mu(d)}{d}$임을 유도했다.
$\therefore \sum_{d|n} \frac{\mu(d)}{d} = \frac{\phi(n)}{n}$
이는 확률론적으로 $n$ 이하의 임의의 수가 $n$과 서로소일 확률과 연관된다.