</>sillysillyman
♾️알고리즘

에라토스테네스의 체 - 메르텐스 제2정리 증명

에라토스테네스의 체의 시간복잡도 의 근거가 되는 메르텐스의 제2정리를, 체비셰프 상한, 폰 망골트 함수, 아벨 합산법 순서로 증명한다

sillysillyman··11분 읽기

메르텐스의 제2정리 증명

⚠️ 이 글은 나의 수학적 이해를 바탕으로 쓴 글이 아니다. 에라토스테네스의 체의 시간복잡도를 공부하다가 메르텐스의 제2정리가 필요하다는 것을 알게 되었는데, 수학 전공자가 아니다 보니 각 단계의 계산을 따라가는 것은 가능해도, 왜 이 도구들을 꺼내야 하는지 그 증명 전략의 동기를 스스로 떠올리기는 어려웠다. 그래서 전적으로 AI의 도움을 받아 증명 과정을 정리했다. 증명의 정확성을 내가 완전히 보장할 수는 없지만, 이 증명이 궁금한 분들에게 참고가 되었으면 하는 마음으로 공유한다.

메르텐스의 제2정리란

메르텐스의 제2정리(Mertens' second theorem)는 소수의 역수의 합이 어떤 속도로 증가하는지를 정확히 알려주는 정리이다:
∑p≤N1p=ln⁡ln⁡N+M+O(1ln⁡N)\sum_{p \leq N} \frac{1}{p} = \ln \ln N + M + O\left(\frac{1}{\ln N}\right)
여기서 M≈0.2615M \approx 0.2615은 마이셀-메르텐스(Meissel–Mertens) 상수이다. 이 등식에 의해 소수의 역수의 합은 정확히 Θ(log⁡log⁡N)\Theta(\log \log N)으로 증가한다.
이 정리가 왜 중요한지 간단히 언급하면, 에라토스테네스의 체의 시간복잡도가 O(Nlog⁡log⁡N)O(N \log \log N)임을 증명하는 핵심 근거가 된다. 자세한 내용은 이전 글 에라토스테네스의 체 - 구현과 시간복잡도를 참조하자.
증명은 세 단계로 진행한다.

1단계: ϑ(N)=O(N)\vartheta(N) = O(N) (체비셰프 상한)

체비셰프 세타 함수(Chebyshev theta function)를 정의한다:
ϑ(N)=∑p≤Nln⁡p\vartheta(N) = \sum_{p \leq N} \ln p
NN 이하의 모든 소수에 자연로그를 취한 것의 합이다. 이 함수에 대해 ϑ(N)≤2Nln⁡2\vartheta(N) \leq 2N \ln 2임을 보인다.
핵심은 이항계수 (2nn)\binom{2n}{n}의 크기이다. 이항 정리에 의해:
(1+1)2n=∑k=02n(2nk)≥(2nn)(1 + 1)^{2n} = \sum_{k = 0}^{2n} \binom{2n}{k} \geq \binom{2n}{n}
우변은 (2nn)\binom{2n}{n}을 포함한 모든 항의 합이고, 각 항이 양수이므로 (2nn)≤4n\binom{2n}{n} \leq 4^n이다.
한편, n<p≤2nn < p \leq 2n인 소수 pp는 p≤2np \leq 2n이므로 (2n)!(2n)!에는 인수로 등장하지만, p>np > n이므로 n!n!에는 등장하지 않는다. 따라서 pp는 (2nn)=(2n)!(n!)2\binom{2n}{n} = \frac{(2n)!}{(n!)^2}의 약수이다. 서로 다른 소수들은 서로소이므로 그 곱 역시 (2nn)\binom{2n}{n}의 약수이다. 양의 정수의 약수는 항상 그 수 이하이므로:
∏n<p≤2np≤(2nn)≤(1+1)2n=4n\prod_{n < p \leq 2n} p \leq \binom{2n}{n} \leq (1+1)^{2n}=4^n
양변에 로그를 취하면 곱의 로그는 로그의 합이고 ∑n<p≤2nln⁡p=ϑ(2n)−ϑ(n)\sum_{n < p \leq 2n} \ln p = \vartheta(2n) - \vartheta(n)이므로:
ϑ(2n)−ϑ(n)≤nln⁡4=2nln⁡2\vartheta(2n) - \vartheta(n) \leq n \ln 4 = 2n \ln 2
이를 텔레스코핑하면 (편의상 N=2mN = 2^m이라 하자):
ϑ(N)=ϑ(2m)=∑k=0m−1[ϑ(2k+1)−ϑ(2k)]≤∑k=0m−12k+1ln⁡2<2Nln⁡2\vartheta(N) = \vartheta(2^m) = \sum_{k = 0}^{m - 1} \left[\vartheta(2^{k+1}) - \vartheta(2^{k})\right] \leq \sum_{k = 0}^{m - 1} 2^{k+1} \ln 2 < 2N \ln 2
일반적인 NN에 대해서도 ϑ(N)≤ϑ(2⌈log⁡2N⌉)≤2⋅2⌈log⁡2N⌉ln⁡2≤4Nln⁡2\vartheta(N) \leq \vartheta(2^{\lceil \log_2 N \rceil}) \leq 2 \cdot 2^{\lceil \log_2 N \rceil} \ln 2 \leq 4N \ln 2이므로 ϑ(N)=O(N)\vartheta(N) = O(N)이 성립한다.

2단계: ∑p≤Nln⁡pp=ln⁡N+O(1)\sum_{p \leq N} \frac{\ln p}{p} = \ln N + O(1)

먼저 폰 망골트 함수(von Mangoldt function) Λ(n)\Lambda(n)을 정의한다:
Λ(n)={ln⁡pif n=pk (소수의 거듭제곱)0otherwise\Lambda(n) = \begin{cases} \ln p & \text{if } n = p^k \text{ (소수의 거듭제곱)} \\ 0 & \text{otherwise} \end{cases}
폰 망골트 함수의 핵심 성질은 다음과 같다:
ln⁡n=∑d∣nΛ(d)\ln n = \sum_{d \mid n} \Lambda(d)
예를 들어 ln⁡12=Λ(1)+Λ(2)+Λ(3)+Λ(4)+Λ(6)+Λ(12)=0+ln⁡2+ln⁡3+ln⁡2+0+0=ln⁡4+ln⁡3=ln⁡12\ln 12 = \Lambda(1) + \Lambda(2) + \Lambda(3) + \Lambda(4) + \Lambda(6) + \Lambda(12) = 0 + \ln 2 + \ln 3 + \ln 2 + 0 + 0 = \ln 4 + \ln 3 = \ln 12이다. 이 성질은 소인수분해의 유일성으로부터 증명할 수 있다.
이 성질을 활용하여 ∑n≤Nln⁡n\sum_{n \leq N} \ln n을 두 가지 방식으로 표현한다.
좌변: 스털링 근사(N!≈(Ne)N2πNN! \approx \left(\frac{N}{e}\right)^N \sqrt{2\pi N}, 팩토리얼을 근사하는 공식)에 의해
∑n=1Nln⁡n=ln⁡N!=Nln⁡N−N+O(ln⁡N)\sum_{n = 1}^{N} \ln n = \ln N! = N \ln N - N + O(\ln N)
우변: ln⁡n=∑d∣nΛ(d)\ln n = \sum_{d \mid n} \Lambda(d)를 대입하고, 약수에 대한 합의 순서를 교환하면
∑n=1Nln⁡n=∑n=1N∑d∣nΛ(d)=∑d=1NΛ(d)⌊Nd⌋\sum_{n = 1}^{N} \ln n = \sum_{n = 1}^{N} \sum_{d \mid n} \Lambda(d) = \sum_{d = 1}^{N} \Lambda(d) \left\lfloor \frac{N}{d} \right\rfloor
dd가 nn의 약수인 쌍 (n,d)(n, d)를 세는 순서를 바꾼 것이다. 각 dd에 대해 d∣nd \mid n이고 n≤Nn \leq N인 nn의 개수는 ⌊N/d⌋\lfloor N/d \rfloor개이다.
⌊N/d⌋=N/d−{N/d}\lfloor N/d \rfloor = N/d - \{N/d\} (여기서 {x}\{x\}는 소수 부분, 0≤{x}<10 \leq \{x\} < 1)이므로:
∑d=1NΛ(d)⌊Nd⌋=N∑d=1NΛ(d)d−∑d=1NΛ(d){Nd}\sum_{d = 1}^{N} \Lambda(d) \left\lfloor \frac{N}{d} \right\rfloor = N \sum_{d = 1}^{N} \frac{\Lambda(d)}{d} - \sum_{d = 1}^{N} \Lambda(d) \left\{\frac{N}{d}\right\}
오차항을 처리하자. 0≤{N/d}<10 \leq \{N/d\} < 1이므로:
∣∑d=1NΛ(d){Nd}∣<∑d=1NΛ(d)=ψ(N)\left|\sum_{d=1}^{N} \Lambda(d)\left\{\frac{N}{d}\right\}\right| < \sum_{d=1}^{N} \Lambda(d) = \psi(N)
여기서 ψ(N)=∑n≤NΛ(n)=ϑ(N)+∑pk≤N,  k≥2ln⁡p\psi(N) = \sum_{n \leq N} \Lambda(n) = \vartheta(N) + \sum_{p^k \leq N,\; k \geq 2} \ln p이다. 소수 거듭제곱 부분은:
∑pk≤N,  k≥2ln⁡p≤∑p≤Nln⁡p⋅⌊ln⁡Nln⁡p⌋≤Nln⁡N=O(Nln⁡N)\sum_{p^k \leq N,\; k \geq 2} \ln p \leq \sum_{p \leq \sqrt{N}} \ln p \cdot \left\lfloor \frac{\ln N}{\ln p} \right\rfloor \leq \sqrt{N} \ln N = O(\sqrt{N} \ln N)
1단계에서 ϑ(N)=O(N)\vartheta(N) = O(N)을 보였으므로 ψ(N)=O(N)\psi(N) = O(N)이다. 따라서:
N∑d=1NΛ(d)d=Nln⁡N−N+O(N)N \sum_{d = 1}^{N} \frac{\Lambda(d)}{d} = N \ln N - N + O(N)
양변을 NN으로 나누면:
∑d=1NΛ(d)d=ln⁡N+O(1)\sum_{d = 1}^{N} \frac{\Lambda(d)}{d} = \ln N + O(1)
이제 Λ(d)/d\Lambda(d)/d의 합에서 소수 항과 소수 거듭제곱 항을 분리한다:
∑d=1NΛ(d)d=∑p≤Nln⁡pp+∑pk≤N,  k≥2ln⁡ppk\sum_{d = 1}^{N} \frac{\Lambda(d)}{d} = \sum_{p \leq N} \frac{\ln p}{p} + \sum_{p^k \leq N,\; k \geq 2} \frac{\ln p}{p^k}
소수 거듭제곱 항은 유계 상수이다. p≥2p \geq 2이므로 11−p−1=pp−1≤2\frac{1}{1-p^{-1}} = \frac{p}{p-1} \leq 2임을 이용하면:
∑pk≤N,  k≥2ln⁡ppk≤∑p∑k=2∞ln⁡ppk=∑pln⁡pp2⋅11−p−1≤∑p2ln⁡pp2<∑n=2∞2ln⁡nn2<∞\sum_{p^k \leq N,\; k \geq 2} \frac{\ln p}{p^k} \leq \sum_{p} \sum_{k = 2}^{\infty} \frac{\ln p}{p^k} = \sum_{p} \frac{\ln p}{p^2} \cdot \frac{1}{1 - p^{-1}} \leq \sum_{p} \frac{2\ln p}{p^2} < \sum_{n = 2}^{\infty} \frac{2 \ln n}{n^2} < \infty
따라서:
∑p≤Nln⁡pp=ln⁡N+O(1)\sum_{p \leq N} \frac{\ln p}{p} = \ln N + O(1)

3단계: 아벨 합산법으로 ∑1p\sum \frac{1}{p}으로 변환

∑p≤N1p\sum_{p \leq N} \frac{1}{p}를 구하고 싶은데, 2단계에서 알고 있는 것은 ∑p≤Nln⁡pp\sum_{p \leq N} \frac{\ln p}{p}이다. 두 식의 관계는:
1p=ln⁡pp⋅1ln⁡p\frac{1}{p} = \frac{\ln p}{p} \cdot \frac{1}{\ln p}
이므로 1ln⁡p\frac{1}{\ln p}라는 가중치를 분리해내야 한다. 이를 위해 아벨 합산법(Abel summation)을 사용한다.
아벨 합산법: 수열 an{a_n}과 연속미분가능 함수 ff에 대해, A(x)=∑n≤xanA(x) = \sum_{n \leq x} a_n이라 하면:
∑n≤Nanf(n)=A(N)f(N)−∫1NA(t)f′(t)dt\sum_{n \leq N} a_n f(n) = A(N)f(N) - \int_1^{N} A(t) f'(t) dt
여기서 ap=ln⁡ppa_p = \frac{\ln p}{p} (소수일 때), an=0a_n = 0 (소수가 아닐 때), f(t)=1ln⁡tf(t) = \frac{1}{\ln t}로 놓는다.
A(x)=∑p≤xln⁡pp=ln⁡x+R(x),  R(x)=O(1)A(x) = \sum_{p \leq x} \frac{\ln p}{p} = \ln x + R(x), \; R(x) = O(1)
f′(t)=−1t(ln⁡t)2f'(t) = -\frac{1}{t(\ln t)^2}이므로:
∑p≤N1p=∑p≤Nln⁡pp⋅1ln⁡p=A(N)ln⁡N−∫2NA(t)⋅(−1t(ln⁡t)2)dt=A(N)ln⁡N+∫2NA(t)t(ln⁡t)2dt\begin{aligned} \sum_{p \leq N} \frac{1}{p} &= \sum_{p \leq N} \frac{\ln p}{p} \cdot \frac{1}{\ln p} \\ &= \frac{A(N)}{\ln N} - \int_2^{N} A(t) \cdot \left(-\frac{1}{t(\ln t)^2}\right) dt \\ &= \frac{A(N)}{\ln N} + \int_2^{N} \frac{A(t)}{t(\ln t)^2} dt \end{aligned}
A(t)=ln⁡t+R(t)A(t) = \ln t + R(t)를 대입하면:
=ln⁡N+R(N)ln⁡N+∫2Nln⁡t+R(t)t(ln⁡t)2dt=1+R(N)ln⁡N+∫2N1tln⁡tdt+∫2NR(t)t(ln⁡t)2dt\begin{aligned} &= \frac{\ln N + R(N)}{\ln N} + \int_2^{N} \frac{\ln t + R(t)}{t(\ln t)^2} dt \\ &= 1 + \frac{R(N)}{\ln N} + \int_2^{N} \frac{1}{t \ln t} dt + \int_2^{N} \frac{R(t)}{t(\ln t)^2} dt \end{aligned}
각 항을 정리하면:
  • R(N)ln⁡N=O(1ln⁡N)\frac{R(N)}{\ln N} = O\left(\frac{1}{\ln N}\right)
  • ∫2N1tln⁡tdt=ln⁡ln⁡N−ln⁡ln⁡2\int_2^{N} \frac{1}{t \ln t} dt = \ln \ln N - \ln \ln 2 (1tln⁡t\frac{1}{t \ln t}의 부정적분은 ln⁡ln⁡t\ln \ln t)
  • ∫2NR(t)t(ln⁡t)2dt\int_2^{N} \frac{R(t)}{t(\ln t)^2} dt는 R(t)=O(1)R(t) = O(1)이고 ∫2∞1t(ln⁡t)2dt<∞\int_2^{\infty} \frac{1}{t(\ln t)^2} dt < \infty이므로 수렴한다
첫째 항의 11, 둘째 항의 −ln⁡ln⁡2-\ln \ln 2, 셋째 항으 ㅣ수렴값을 합쳐서 상수 MM이라 하자.
따라서:
∑p≤N1p=ln⁡ln⁡N+M+O(1ln⁡N)\sum_{p \leq N} \frac{1}{p} = \ln \ln N + M + O\left(\frac{1}{\ln N}\right)
이것이 메르텐스의 제2정리이다. 여기서 M≈0.2615M \approx 0.2615은 마이셀-메르텐스(Meissel–Mertens) 상수이다. ■\blacksquare

참고

목록으로