디리클레 등차수열 정리

디리클레 등차수열 정리(Dirichlet's theorem on arithmetic progressions)는 소수의 개수가 무한하다는 정리를 자연수 집합에서 자연수의 등차수열로 확장한 정리이다.

진술

첫 항과 공차가 자연수이고 이들 두 수가 서로소인 자연수의 등차수열이 주어져 있을 때, 이 수열에는 무한히 많은 소수가 포함되어 있다.

즉 [math]\displaystyle{ A(a, b)=\{x=a+bn| n \in \mathbb{N} \cup \{0\}\}, \gcd(a, b)=1 }[/math]이 주어져 있고 [math]\displaystyle{ \mathbb{P} }[/math]를 소수의 집합이라 할 때, [math]\displaystyle{ P(a, b)=A(a, b) \cap \mathbb{P} }[/math]는 무한집합이라 쓸 수 있다.

더 나아가 이 등차수열 내 소수의 역수들을 모두 합하면 발산한다. 이는 바로 위의 진술보다 강한 정리이다.

[math]\displaystyle{ \sum_{p \in P(a, b)} \frac{1}{p} =\infty }[/math]

증명

이와 관련한 내용은 디리클레 L-함수에서 볼 수 있습니다.

0 이상의 정수 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ N=a+bn }[/math]인 소수가 무한하다는 사실을 증명할 때, 디리클레 L-함수를 도입한다. 이때 이용하는 디리클레 지표의 주기는 [math]\displaystyle{ b }[/math]이고, 함수의 변수인 [math]\displaystyle{ s }[/math]는 1보다 큰 실수이다.

[math]\displaystyle{ L(s, \chi)=\sum_{n=1}^{\infty} \frac{\chi(n)}{n^s}=\prod_{p \in \mathbb{P}} \frac{1}{1-\chi(p)p^{-s}} }[/math]

이 함수의 로그를 취하면

[math]\displaystyle{ \ln L(s, \chi)=\sum_{p \in \mathbb{P}} (-\ln(1-\chi(p)p^{-s})) }[/math]

여기서 급수 내 각 항은 [math]\displaystyle{ \gcd(b, p)=1 }[/math]일 때 [math]\displaystyle{ |\chi(p)|=1 }[/math]이고 [math]\displaystyle{ s\gt 1 }[/math]일 때 [math]\displaystyle{ |p^{-s}|\lt 1 }[/math]이므로, 로그함수의 테일러 급수를 적용할 수 있다.

[math]\displaystyle{ -\ln(1-x)=\sum_{m=1}^{\infty}\frac{x^m}{m} (|x|\lt 1) }[/math]

[math]\displaystyle{ -\ln(1-\chi(p)p^{-s})=\sum_{m=1}^{\infty}\frac{\chi(p^m)}{mp^{ms}} }[/math]

따라서 [math]\displaystyle{ \ln L(s, \chi)=\sum_{p \in \mathbb{P}} \sum_{m=1}^{\infty}\frac{\chi(p^m)}{mp^{ms}} }[/math]

셋째 줄은 [math]\displaystyle{ \ln L(s, \chi)=\sum_{p \in \mathbb{P}} \frac{\chi(p)}{p^s}+O(1) }[/math]의 꼴로 바꿀 수 있다. 여기서 [math]\displaystyle{ O(1) }[/math] 항은 [math]\displaystyle{ m \geq 2 }[/math]에 해당하는 항들의 급수를 합한 것으로, 특정 값에 수렴한다. ([math]\displaystyle{ s\gt 1 }[/math]일 때 [math]\displaystyle{ L(s, \chi), \sum_{p \in \mathbb{P}} \frac{\chi(p)}{p^s} }[/math]도 수렴)

이어서 주기가 [math]\displaystyle{ b }[/math]인 디리클레 지표에 대해 [math]\displaystyle{ \chi(n)=\chi(n+b) }[/math]이므로, [math]\displaystyle{ 1 \leq r \leq b, p \equiv r \pmod b }[/math]인 소수별로 항들을 묶어서 쓸 수 있다.

[math]\displaystyle{ \sum_{p \in \mathbb{P}} \frac{\chi(p)}{p^s}=\sum_{r=1}^b \chi(r) \sum_{p \in P(r, b)} \frac{1}{p^s} }[/math]

[math]\displaystyle{ \ln L(s, \chi)=\sum_{r=1}^b \chi(r) \sum_{p \in P(r, b)} \frac{1}{p^s}+O(1) }[/math] (★)

그 다음 디리클레 지표의 성질을 하나 불러온다. [math]\displaystyle{ \varphi(b) }[/math]는 오일러 피 함수이다.

[math]\displaystyle{ \sum_{\chi}\chi(r)= \begin{cases}\varphi(b) & (r \equiv 1 \pmod b) \\ 0 & (\text{o/w})\end{cases} }[/math]

(★) 표시된 식에서 [math]\displaystyle{ r=a, \gcd(a, b)=1 }[/math]인 항만을 골라내고 싶다면 이 식에 각 [math]\displaystyle{ \chi }[/math]마다 [math]\displaystyle{ \chi(a') }[/math]을 곱한 식들을 더하면 된다. 여기서 [math]\displaystyle{ aa' \equiv 1 \pmod b }[/math]이다.

[math]\displaystyle{ \sum_{\chi}\chi(a')\ln L(s, \chi) =\sum_{\chi}\sum_{r=1}^b \chi(a')\chi(r) \sum_{p \in P(r, b)} \frac{1}{p^s}+O(1) =\sum_{r=1}^b \sum_{\chi}\chi(a'r) \sum_{p \in P(r, b)} \frac{1}{p^s}+O(1) }[/math]

이때 앞의 시그마 두 개 표시는 [math]\displaystyle{ a'r \equiv 1 \pmod b, r=a }[/math]인 항만 0이 아닌 값으로 남으며 그 값은 [math]\displaystyle{ \varphi(b) }[/math]이다.

[math]\displaystyle{ \sum_{\chi}\chi(a')\ln L(s, \chi) =\varphi(b)\sum_{p \in P(a, b)} \frac{1}{p^s}+O(1) }[/math]

좌변을 [math]\displaystyle{ \ln L(s, \chi_0)+\sum_{\chi \neq \chi_0}\chi(a')\ln L(s, \chi) }[/math]와 같이 주지표 항과 주지표가 아닌 항들로 나눌 때, [math]\displaystyle{ s \to 1^+ }[/math]일 때 [math]\displaystyle{ L(s, \chi_0) }[/math]는 발산하지만 나머지 함수들은 정칙함수이기에 발산하지 않는다. 곧, 좌변은 발산한다는 뜻이며, 나아가 우변의 [math]\displaystyle{ \sum_{p \in P(a, b)} \frac{1}{p^s} }[/math] 항도 [math]\displaystyle{ s \to 1^+ }[/math]에서 발산한다.

이를 달리 표현하면 [math]\displaystyle{ \sum_{p \in P(a, b)} \frac{1}{p}=\infty }[/math]로, [math]\displaystyle{ p=a+bn }[/math] 꼴의 소수의 역수들의 합은 발산한다. 따라서 이들 소수의 개수 역시 무한하다.

특수한 등차수열

모든 등차수열에 대한 디리클레 정리의 증명은 꽤 복잡하지만, 특수한 등차수열에서는 "소수는 무한하다"는 정리의 유클리드의 증명 방식을 적절히 변형해서 이끌어낼 수 있다.

이를테면 [math]\displaystyle{ p=4n+3 }[/math] 꼴의 소수가 무한하다는 사실을 증명하고 싶다면, 귀류법으로 소수가 [math]\displaystyle{ P(3, 4)=\{p_1, p_2, \cdots p_k\} }[/math]로 유한하다고 가정하고 다항식 [math]\displaystyle{ f(x)=4x-1 }[/math]을 상정한다. 그 다음 주어진 모든 소수들의 곱인 [math]\displaystyle{ M=p_1 p_2 \cdots p_k }[/math]을 생각할 수 있다.

그러면 [math]\displaystyle{ f(M)=4M-1 }[/math]은 1보다 큰 자연수이고, 주어진 소수 중 어떤 것으로도 나누어지지 않는다. 따라서 앞서 가정한 목록에는 없는 새로운 소수가 존재해서 [math]\displaystyle{ p \mid f(M) }[/math]을 만족한다. 그런데 [math]\displaystyle{ f(M) }[/math]은 홀수이기에 [math]\displaystyle{ p \equiv \pm 1 \pmod 4 }[/math]이고, [math]\displaystyle{ f(M) \equiv 3 \pmod 4 }[/math]이므로 [math]\displaystyle{ f(M) }[/math]의 소인수 중 적어도 하나는 [math]\displaystyle{ 4n+3 }[/math] 꼴이어야 한다. 따라서 이 형태의 소수가 [math]\displaystyle{ P(3, 4) }[/math]의 원소 외에도 더 존재하게 되므로, 주어진 "유한하다"는 가정은 모순이다.

이 증명은 [math]\displaystyle{ p=6n+5 }[/math]의 형태에서도 적용이 된다. [math]\displaystyle{ P(5, 6) }[/math]의 원소가 유한하다고 가정하고 [math]\displaystyle{ f(x)=6x-1 }[/math]로 놓은 다음 같은 방법으로 모순을 이끌어내면 된다.

그렇다면 [math]\displaystyle{ p=4n+1 }[/math]의 경우는? 이 그룹은 피타고라스 소수 문서에 소개되어 있듯이 [math]\displaystyle{ f(x)=x^2+1 }[/math]로 놓는다. [math]\displaystyle{ P(1, 4) }[/math]가 유한집합이라 가정하고, [math]\displaystyle{ p \mid f(M)=M^2+1 }[/math]이면 [math]\displaystyle{ p \not\in P(1, 4), M^2 \equiv -1 \pmod p }[/math], 즉 -1이 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여이므로 [math]\displaystyle{ p \equiv 1 \pmod 4 }[/math]이다. 즉 [math]\displaystyle{ 4n+1 }[/math] 꼴의 소수가 처음에 가정한 [math]\displaystyle{ P(1, 4) }[/math]의 목록 밖에도 존재하므로 모순이다.

이 사실은 [math]\displaystyle{ p=6n+1 }[/math]의 경우도 마찬가지. [math]\displaystyle{ f(x)=x^2+3 }[/math]으로 놓고 -3이 법 [math]\displaystyle{ p }[/math]에 대한 이차잉여라는 점을 이용하면 이 그룹도 개수가 무한함을 알 수 있다.

물론 이 방법은 [math]\displaystyle{ \varphi(4)=\varphi(6)=2 }[/math]이고 소수의 형태가 [math]\displaystyle{ 4n \pm 1, 6n \pm 1 }[/math]과 같이 두 그룹으로 나뉘어서 증명이 되는 것이다. 반면 [math]\displaystyle{ 8n+\{1, 3, 5, 7\} }[/math]은 네 그룹으로 쪼개지므로 앞서 다항식 [math]\displaystyle{ f(x) }[/math]의 차수를 더 올려야 한다. 그룹 수가 많아질수록 다항식의 모양도 복잡해지므로 이러한 방식은 '일반적인 등차수열'로 확장하지는 못한다.