2.1 산술 함수 (Arithmetic Functions)

산술 함수는 모든 양의 정수 집합을 정의역으로 하는 복소함수입니다. 이들은 수의 구조적 성질을 수치화하며, 특히 곱셈적 함수(Multiplicative Functions)는 소인수분해의 유일성과 결합하여 강력한 위력을 발휘합니다.

1. 주요 산술 함수

약수 함수 (Divisor Function)

$\sigma_k(n)$은 $n$의 모든 양의 약수의 $k$차 거듭제곱의 합을 나타냅니다.

$\tau(n) = \sigma_0(n)$: 약수의 개수
$\sigma(n) = \sigma_1(n)$: 약수의 총합

오일러 파이 함수 (Euler's Phi Function)

$\phi(n)$은 $1 \le k \le n$인 정수 중 $n$과 서로소인 수의 개수입니다.

$$\phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)$$

2. 뫼비우스 함수 (Möbius Function)

뫼비우스 함수 $\mu(n)$은 다음과 같이 정의되며, 뫼비우스 반전 공식의 핵심입니다.

$$\mu(n) = \begin{cases} 1 & \text{if } n=1 \\ (-1)^k & \text{if } n \text{ is the product of } k \text{ distinct primes} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases}$$

주요 성질: $\sum_{d|n} \mu(d) = [n=1]$ (크로네커 델타와 유사한 역할)

3. 디리클레 합성 (Dirichlet Convolution)

두 산술 함수 $f$와 $g$를 결합하여 새로운 함수를 만드는 연산입니다.

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

Properties

교환법칙: $f * g = g * f$
결합법칙: $(f * g) * h = f * (g * h)$
항등원: $\epsilon(n) = [n=1]$ 에 대해 $f * \epsilon = f$
곱셈적 성질 보존: $f, g$가 곱셈적 함수이면 $f * g$도 곱셈적입니다.

4. 뫼비우스 반전 공식 (Möbius Inversion Formula)

두 함수 $f$와 $F$ 사이의 관계를 역으로 계산할 수 있게 해줍니다.

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

이를 디리클레 합성 기호로 쓰면 매우 간단해집니다: $F = f * I \iff f = F * \mu$ (단, $I(n)=1$)