ℤ정수론
IV. 곱셈 구조 · 8/16

수론적 함수

φ·σ·τ, 곱셈적 함수, 뫼비우스 반전

읽음 0/0 갱신 2026-06-30

개요 — 동기·문제의식

$360$의 약수는 몇 개인가? 그 약수들을 다 더하면 얼마인가? $360$과 서로소인 수는 몇 개인가? 세 질문 모두 $360=2^3\cdot3^2\cdot5$ 라는 소인수분해 하나만 알면 — 약수를 일일이 나열하지 않고도 — 즉시 답이 나온다. 이것이 가능한 이유는 세 질문에 답하는 함수 $\tau$(약수 개수), $\sigma$(약수 합), $\varphi$(서로소 개수)가 모두 곱셈적(multiplicative) 이라는 공통 구조를 갖기 때문이다: 서로소인 두 수에 대해 함숫값이 곱으로 분해된다. 이 한 가지 성질이 "소인수분해 → 소수거듭제곱별 계산 → 곱"이라는 만능 계산 전략을 정당화한다.

이 페이지는 정수에 정의된 이런 산술함수(arithmetic function) 들을 다룬다. $\varphi$는 이미 오일러 φ 함수와 정리에서 다뤘으니 여기서는 $\tau,\sigma$ 를 중심으로 곱셈성의 일반 이론, φ의 약수 합 항등식, 그리고 완전수와의 연결을 살펴본다.

직관

"곱셈적"이라는 말이 이상하게 들릴 수 있다 — 함수가 덧셈이 아니라 곱셈을 보존한다니? 비결은 약수의 구조 자체가 소인수분해를 따라 곱으로 갈라진다는 데 있다. $n=mn'$ ($\gcd(m,n')=1$)의 약수는 정확히 "$m$의 약수 $\times$ $n'$의 약수"의 모든 조합이다 — 예를 들어 $12=4\cdot3$의 약수 $\{1,2,3,4,6,12\}$ 는 $4$의 약수 $\{1,2,4\}$ 와 $3$의 약수 $\{1,3\}$ 의 곱 $\{1\cdot1,1\cdot3,2\cdot1,2\cdot3,4\cdot1,4\cdot3\}=\{1,3,2,6,4,12\}$ 와 정확히 같다(서로소이므로 중복이 없다). 약수를 세든(τ) 더하든(σ) 서로소이든(φ) 이런 "곱 구조"를 따라가면 함숫값도 곱으로 쪼개진다 — 중국인의 나머지 정리이 보장하는 분해 가능성의 또 다른 얼굴이다.

정의

약수 개수 함수 $\tau(n)$ (또는 $d(n)$): $n$의 양의 약수의 개수. 약수 합 함수 $\sigma(n)=\sum_{d\mid n}d$: $n$의 모든 양의 약수의 합.1 Euler φ 함수 $\varphi(n)$: 오일러 φ 함수와 정리 참조.

용어 정의 예 ($n=12$의 약수 $1,2,3,4,6,12$)
곱셈적(multiplicative) $\gcd(m,n)=1\Rightarrow f(mn)=f(m)f(n)$ $\tau,\sigma,\varphi$ 모두 해당
완전 곱셈적(completely multiplicative) 모든 $m,n$ (서로소 아니어도) 에서 $f(mn)=f(m)f(n)$ $f(n)=n^k$, Liouville $\lambda(n)$
$\tau(12)$ $6$ $1,2,3,4,6,12$ — 6개
$\sigma(12)$ $28$ $1+2+3+4+6+12=28$

곱셈적과 완전 곱셈적의 차이. $\tau,\sigma,\varphi$ 는 곱셈적이지만 완전 곱셈적은 아니다 — $\gcd(m,n)>1$ 이면 공식이 깨진다(예: $\varphi(4)=2\ne\varphi(2)^2=1$). 반면 $f(n)=n$ 같은 완전 곱셈적 함수는 서로소 여부와 무관하게 항상 $f(mn)=f(m)f(n)$.

주요 정리

정리 (곱셈적 함수의 소수거듭제곱 분해). $f$ 가 곱셈적이고 $n=p_1^{e_1}\cdots p_r^{e_r}$ 이면2 $$f(n)=\prod_{i=1}^r f(p_i^{e_i}).$$

증명 보기

증명 아이디어. 서로 다른 소인수의 거듭제곱들은 쌍마다 서로소이므로 곱셈성을 반복 적용. 따라서 곱셈적 함수는 소수거듭제곱에서의 값만 알면 전체가 결정된다.

계산 공식. - $\tau(p^e)=e+1$ ($1,p,p^2,\dots,p^e$ 의 $e+1$개) → $\tau(n)=\prod_i(e_i+1)$. - $\sigma(p^e)=1+p+p^2+\cdots+p^e=\dfrac{p^{e+1}-1}{p-1}$ (등비수열 합) → $\sigma(n)=\prod_i\dfrac{p_i^{e_i+1}-1}{p_i-1}$.3 - $\varphi(p^e)=p^e-p^{e-1}$ → 오일러 φ 함수와 정리.

정리 (φ의 약수 합 항등식). $\displaystyle\sum_{d\mid n}\varphi(d)=n$.4 증명 스케치. $F(n)=\sum_{d\mid n}\varphi(d)$ 라 두면, "곱셈적 함수를 약수에 대해 합한 함수도 곱셈적"이라는 보조정리에 의해 $F$ 도 곱셈적이다. 소수거듭제곱에서 직접 계산하면 망원합으로 $F(p^k)=\varphi(1)+\varphi(p)+\cdots+\varphi(p^k)=1+(p-1)+(p^2-p)+\cdots+(p^k-p^{k-1})=p^k$ 이 나오므로, 곱셈성에 의해 모든 $n$에서 $F(n)=n$.

정리 (완전수와 σ). $n$이 완전수(perfect number) $\iff$ $n$이 자신의 진약수(자기 자신 제외) 합과 같음 $\iff$ $\sigma(n)=2n$.5 Euclid의 완전수 공식: $2^{p-1}-1$ 이 소수(메르센 소수)이면 $2^{p-1}(2^p-1)$ 은 완전수.

Möbius 함수와 반전 공식 (orientation, [synthesis]). $\mu(n)$ 을 $n=1$ 이면 $1$, $n$이 제곱인수($p^2\mid n$)를 가지면 $0$, $n=p_1\cdots p_k$ (서로 다른 소수 $k$개의 곱, 제곱없음)이면 $(-1)^k$ 로 정의하면 $\mu$ 도 곱셈적이며, Möbius 반전 공식 $$g(n)=\sum_{d\mid n}f(d) \quad\Longleftrightarrow\quad f(n)=\sum_{d\mid n}\mu(d)\,g(n/d)$$ 이 성립한다.6 예를 들어 $\sum_{d\mid n}\varphi(d)=n$ (위 정리)에 반전을 적용하면 $\varphi(n)=\sum_{d\mid n}\mu(d)\,(n/d)$ 라는 닫힌 식을 얻는다 — φ의 일반 공식 $n\prod_{p\mid n}(1-1/p)$ 과 동치임을 전개해 확인할 수 있다. 이 함수와 반전 공식은 해석적 정수론의 표준 도구이지만, Silverman 입문서 범위 밖의 orientation으로 다룬다.

예제

예제 1 (기본 계산). $n=12=2^2\cdot3$: $\tau(12)=(2+1)(1+1)=6$, $\sigma(12)=\dfrac{2^3-1}{2-1}\cdot\dfrac{3^2-1}{3-1}=7\cdot4=28$, $\varphi(12)=(4-2)(3-1)=2\cdot2=4$.

예제 2 (큰 수, 세 함수 동시). $n=360=2^3\cdot3^2\cdot5$: $\tau(360)=4\cdot3\cdot2=24$; $\sigma(360)=\dfrac{2^4-1}{1}\cdot\dfrac{3^3-1}{2}\cdot\dfrac{5^2-1}{4}=15\cdot13\cdot6=1170$; $\varphi(360)=4\cdot6\cdot4=96$.

예제 3 (완전수 판정). $n=28=2^2\cdot7$: $\sigma(28)=\dfrac{2^3-1}{1}\cdot\dfrac{7^2-1}{6}=7\cdot8=56=2\cdot28$ → 완전수. Euclid 공식과 비교: $p=3$ (소수), $2^3-1=7$ (메르센 소수) → $2^2\cdot7=28$ ✓ 일치.

예제 4 (완전수가 아님을 확인). $n=12$: $\sigma(12)=28\ne24=2\cdot12$ — 부족수($\sigma(n)<2n$). $n=18=2\cdot3^2$: $\sigma(18)=3\cdot13=39$, $2\cdot18=36$, $39>36$ — 과잉수($\sigma(n)>2n$).

예제 5 (φ 약수 합 항등식 검증). $n=20$: 약수 $1,2,4,5,10,20$, $\varphi$ 값 $1,1,2,4,4,8$, 합 $=1+1+2+4+4+8=20$ ✓.

예제 6 (τ가 홀수인 경우 — 완전제곱수). $n=36=2^2\cdot3^2$: $\tau(36)=3\cdot3=9$ (홀수). $36=6^2$ 은 완전제곱수다 — 우연이 아니라 약수가 $d\leftrightarrow n/d$ 로 짝지어지는데 $d=\sqrt n$ 인 경우만 자기 자신과 짝지어져 홀수개가 남기 때문.

예제 7 (Möbius 함수 값, orientation). $\mu(30)$: $30=2\cdot3\cdot5$ (서로 다른 소수 3개, 제곱없음) → $\mu(30)=(-1)^3=-1$. $\mu(12)$: $12=2^2\cdot3$ ($2^2$ 으로 제곱인수 있음) → $\mu(12)=0$.

흔한 오해와 함정

큰 그림 / 연결

곱셈적 함수의 틀은 정수론 전반에서 반복되는 패턴이다 — 오일러 φ 함수와 정리의 φ, 여기의 $\tau,\sigma$, 그리고 (orientation으로 언급한) Möbius μ 모두 "소인수분해를 알면 즉시 계산"이라는 같은 전략을 공유하며, 이 분해 가능성의 근원은 중국인의 나머지 정리이 보장하는 환 동형 $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ 이다. σ 함수는 mersenne primes perfect numbers에서 완전수·메르센 소수의 분류와 직결되고, φ는 모듈러 거듭제곱과 RSA의 RSA 키 생성에 직접 쓰인다. 더 멀리 보면, 이런 곱셈적 함수들의 합과 평균 행동(예: $\sum_{n\le x}\tau(n)$ 의 점근 공식)은 해석적 정수론의 핵심 주제이며, prime distribution에서 다루는 소수 정리와 같은 계열의 질문(국소적 산술 데이터로부터 대역적 점근 정보 끌어내기)이다. Möbius 함수와 반전 공식은 정수론을 넘어 조합론의 일반적인 "포함-배제 원리"의 한 사례이기도 하다.

연습문제

  1. $\tau(360),\sigma(360),\varphi(360)$ 을 구하라(이미 본문에 나왔으니 스스로 다시 계산해 검증하라).
  2. $\sigma$ 가 곱셈적임을 ($\sigma(mn)=\sigma(m)\sigma(n)$, $\gcd(m,n)=1$) 약수의 구조로부터 보여라.
  3. $\sigma(n)$ 이 홀수일 필요충분조건을 구하라.
  4. $\sum_{d\mid n}\varphi(d)=n$ 을 $n=p^k$ 에서 직접 보여라.
  5. $\tau(n)$ 이 홀수 $\iff$ $n$ 이 완전제곱수임을 보여라.
  6. $n=496$ 이 완전수인지 $\sigma$ 로 판정하라($496=2^4\cdot31$).
  7. $\mu(105)$ 와 $\mu(49)$ 를 구하라.
  8. $\sigma_2(n)=\sum_{d\mid n}d^2$ (제곱약수합)이 곱셈적임을 가정하고 $\sigma_2(12)$ 를 구하라.
힌트 / 정답
  1. $360=2^3\cdot3^2\cdot5$: $\tau=4\cdot3\cdot2=24$; $\sigma=15\cdot13\cdot6=1170$; $\varphi=4\cdot6\cdot4=96$.
  2. $\gcd(m,n)=1$ 이면 $mn$ 의 모든 약수는 $d=d_1d_2$ ($d_1\mid m,\ d_2\mid n$) 형태로 유일하게 분해된다(서로소이므로 중복 없음). 따라서 $\sigma(mn)=\sum_{d_1\mid m,d_2\mid n}d_1d_2=\left(\sum_{d_1\mid m}d_1\right)\left(\sum_{d_2\mid n}d_2\right)=\sigma(m)\sigma(n)$.
  3. $\sigma(p^e)=1+p+\cdots+p^e$ 가 홀수이려면: $p=2$ 이면 모든 항이($2^k$, $k\ge1$은 짝수, $1$은 홀수) 합이 홀수 1개+짝수들 → 항상 홀수. $p$ 홀수이면 각 항의 홀짝이 동일($p^k$는 항상 홀수)하므로 $e+1$ 개 홀수항의 합 — $e$ 가 짝수일 때만(항 개수 $e+1$ 홀수) 합이 홀수. 종합: $n=2^a\cdot m^2$ ($m$ 홀수, 즉 $n$ 또는 $n/2$ 가 완전제곱수)일 때 $\sigma(n)$ 홀수.
  4. $\sum_{i=0}^k\varphi(p^i)=\varphi(1)+\sum_{i=1}^k(p^i-p^{i-1})=1+(p^k-1)=p^k$ (망원합으로 중간항이 다 소거).
  5. 약수들이 $d\leftrightarrow n/d$ 로 짝지어지는데, $d=n/d$ (즉 $d=\sqrt n$)인 약수는 자기 자신과만 짝지어져 쌍이 안 만들어진다. 이런 약수가 존재하는 것은 $n$이 완전제곱수일 때뿐이므로, 그때만 약수 개수가 홀수.
  6. $\sigma(496)=\sigma(2^4)\sigma(31)=(2^5-1)\cdot32=31\cdot32=992=2\cdot496$ → 완전수(Euclid 공식: $p=5$, $2^5-1=31$ 메르센 소수, $2^4\cdot31=496$).
  7. $105=3\cdot5\cdot7$ (서로 다른 소수 3개) → $\mu(105)=(-1)^3=-1$. $49=7^2$ (제곱인수 있음) → $\mu(49)=0$.
  8. $\sigma_2(p^e)=1+p^2+p^4+\cdots+p^{2e}$. $12=2^2\cdot3$: $\sigma_2(4)=1+4+16=21$, $\sigma_2(3)=1+9=10$ → $\sigma_2(12)=21\cdot10=210$.

관련 개념

  1. 원전 소개 — Silverman ch.15 [synthesis] — 약수 합 함수 σ(n)의 정의; 완전수와의 관계는 같은 장. ↩

  2. 원전 소개 — Silverman ch.27 [synthesis] — 곱셈적 함수의 정의(Exercise 27.1)와, 곱셈적 함수가 소수거듭제곱에서의 값으로 완전히 결정된다는 일반 원리. ↩

  3. 원전 소개 — Silverman ch.15 [synthesis] — $\sigma(p^k)=(p^{k+1}-1)/(p-1)$ 공식; τ(약수 개수) 공식은 같은 패턴의 [synthesis] 확장. ↩

  4. 원전 소개 — Silverman ch.27 / Theorem 27.2 — "Euler's Phi Function Summation Formula. Let d1,...,dr be the divisors of n. Then φ(d1)+φ(d2)+···+φ(dr)=n." 곱셈적 함수의 약수합도 곱셈적이라는 보조정리(Lemma 27.1)로 증명. ↩

  5. 원전 소개 — Silverman ch.15 / Theorem 15.1 — "Euclid's Perfect Number Formula. If 2^p−1 is a prime number, then 2^(p−1)(2^p−1) is a perfect number." 완전수의 정의(자기 진약수의 합과 같은 수)도 같은 장. ↩

  6. 원전 소개 — Silverman ch.27 [synthesis] — Möbius 함수 μ(n)과 반전 공식은 Silverman 입문서 범위를 넘는 orientation 내용(책은 Liouville λ 함수를 연습문제로 다룰 뿐 μ를 명시적으로 도입하지 않음); 정의·반전 공식은 해석적 정수론의 표준 결과를 종합. ↩