| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
算術函數 / arithmetic function자연수 혹은 정수 집합 및 그 부분집합에서 실수/복소수로 가는 함수들 중, 정수론에서 빈번하게 쓰이는 함수들을 말한다.
대부분의 산술함수는 정수의 성질을 연구하기 위해 등장한 함수들로, 일반적인 수열이나 함수랑은 다른 정수론만에서의 고유한 방식으로 탐구된다.
2. 산술함수의 성질
2.1. 승법성
산술함수 [math(f : \mathbb{N} \rightarrow \mathbb{C})]가 승법 함수 및 곱셈적 함수(multiplicative function)라는 것은, 서로소인 [math(m,n)]에 대해 [math(f(mn) = f(m) f(n))]이란 것을 의미한다. 승법 함수는 소수의 거듭제곱꼴 [math(p^e)]에서의 값을 알면 모든 값을 알 수 있다. 약수의 개수, 합, 오일러 파이 함수 등 상당히 많은 함수들이 승법성을 만족시킨다.완전 승법 함수 및 완전 곱셈적 함수(completely multiplicative function)는 위 조건이 모든 [math(m,n)]에 대해 만족되는 함수이고, 이 경우에는 소수 위에서의 값만 알아도 충분하다. 완전 승법 함수로는 [math(n)]의 거듭제곱 꼴 외에도 디리클레 지표(Dirichlet character) 등등이 있다.
2.2. 디리클레 합성곱
산술함수 [math(a,b)]의 디리클레 합성곱 [math(c = a * b)]는[math(\displaystyle c(n) = \sum_{d \vert n} a(d) b\left( \frac{n}{d} \right) = \sum_{de=n} a(d) b(e) )]
로 정의된다. 이 디리클레 합성곱은 다음의 성질을 지닌다.- 결합법칙, 교환법칙, 합과 상수배에 대한 분배법칙이 성립한다.
- 항등원은 [math(n=1)]에서 1의 값을 가지고 나머지에선 0인 함수이다.[1]
- 함수 [math(a)]의 역원이 존재할 필요충분조건은 [math(a(0) \neq 0)]이다.
[math(b = 1 * a \Rightarrow a = \mu * b)]
이를 풀어쓰면 다음과 같다.[math(\displaystyle b(n) = \sum_{d \vert n} a(d) \Rightarrow a(n) = \sum_{d \vert n} b\left( \frac{n}{d} \right) \mu(d) )]
이를 뫼비우스 반전 공식(Möbius inversion formula)이라 부른다.2.3. 디리클레 급수
산술함수 [math(a(n))]의 디리클레 급수(Dirichlet series)는 [math( \sum a(n) n^{-s} )]로 정의된다. 산술함수가 다항식 이하의 성장성을 보일 경우 이 급수는 특정 범위에서 수렴하고, 그렇지 않으면 단순히 형식적인 표현으로 간주된다.디리클레 급수는 정수의 곱에 대한 성질과 여러 방식으로 관련을 맺고 있다. 예로 승법 함수의 경우 디리클레 급수는 소수 [math(p)]에 대한 곱들로 나타낼 수 있고, 이 소수 [math(p)]에 대한 인수가 유한한 항으로 나타낼 수 있을 때 오일러 곱(Euler product)이 존재한다고 표현한다. 대표적인 예시로 리만 제타 함수의 오일러 곱
[math(\displaystyle \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p\, \in\,\mathbb P} \frac{1}{1-p^{-s}} )]
이 있다. 또한 디리클레 합성곱이 디리클레 급수에서는 곱으로 대응되는 된다는 성질이 있어서, 약수와 관련된 성질을 다룰 경우 이 급수가 자연스럽게 등장하는 경우가 많다.한편으로 디리클레 급수는 [math(x = \log n)] 위에서의 이산 질량 분포의 라플라스 변환의 일종으로 간주될 수 있다. 복소해석학에 익숙하다면 라플라스 변환의 역변환인 멜린 변환(Mellin transform)을 통해 디리클레 급수에서 산술함수의 합에 대한 정보를 이끌어낼 수 있고, 이 사고방식은 리만 가설 이후 현재까지의 해석적 정수론의 주 패러다임이 되어 왔다.
물론 산술함수의 생성함수로 디리클레 급수만 쓰이는 건 아니고, 기존 일반 생성함수나 세타 급수(theta series) [math( \sum_n a_n e^{-n^2 \tau + 2 \pi i n z} )] 등등 다른 급수를 생각하는 경우도 많다.
3. 주요 산술함수들의 목록
별도의 언급이 없으면 함수들의 정의역은 자연수(양의 정수)로 간주한다. 이 목록 외에도 무수히 많은 산술함수들이 있다. [math(n)]의 소인수분해 표현을[math(\displaystyle n=\prod_{i=1}^{t} p_i^{e_i})]
이라 하자.- 약수의 개수 [math(d(n))] 혹은 [math(\tau(n))]
[math(\displaystyle d(n) := \sum_{d \vert n} 1 = \sum_{ab=n} 1 = \prod_{i=1}^{t}(e_i+1) = 1 * 1)]
- 디리클레 약수 함수 [math(d_k(n))] 혹은 [math(\tau_k(n))]
[math(\displaystyle d_k(n) := \sum_{a_1 a_2 \cdots a_k =n} 1 = \prod_{i=1}^{t} \binom{e_i+k-1}{k-1} =1*\cdots*1(k \text{ times}) )]
- 소인수의 개수 [math(\Omega(n))], 서로 다른 소인수의 개수 [math(\omega(n))]
[math(\displaystyle \Omega(n) := \sum_{p^k \vert n} 1= \sum e_i, \quad \omega(n) := \sum_{p \vert n} 1 = t)]
- 약수의 합 [math(\sigma(n))]
[math(\displaystyle \sigma(n) := \sum_{d \vert n} d = \prod_i \frac{p_i^{e_i+1}-1}{p_i-1} = 1*n)]
- 약수의 거듭제곱의 합 [math(\sigma_k(n))]
[math(\displaystyle \sigma_k(n) := \sum_{d \vert n} d^k = \prod_i \frac{p_i^{k(e_i+1)}-1}{p_i^k-1} = 1 * n^k)]
- 오일러 파이 함수 [math(\varphi(n))]
[math(\displaystyle \varphi(n) := \sum_{1 \le a \le n, \mathrm{gcd}(a,n)=1} 1 = n \prod_{p \vert n}(1-\frac{1}{p}) = n * \mu(n) )]
- 뫼비우스 함수 [math(\mu(n))]
[math(\displaystyle \mu(n) := \begin{cases} 1 & \text{if } n=1 \\(-1)^t & \text{if } n = p_1 p_2 \cdots p_t, \text{ product of distinct primes} \\ 0 & \text{otherwise} \end{cases}, \quad 1 * \mu(n) = \delta_{n0})]
- 디리클레 지표(Dirichlet character) [2]
- 르장드르 기호 및 야코비 기호: 정의는 이차 잉여 항목을 참고.
- 힐베르트 기호
- 소수 계량 함수와 체비쇼프 함수 2종
- [math(\pi(x), \psi(x), \vartheta(x))] [3]
- 폰 망골트 함수 [math(\Lambda(n))]
[math(\displaystyle \pi(x) := \sum_{p \le x} 1, \quad \psi(x) := \sum_{p^k \le x} \log p, \quad \vartheta(x) := \sum_{p \le x} \log p)]
[math(\displaystyle \Lambda(n) := \mu * \log(n) = \begin{cases} \log p & \text{if } n = p^k \\ 0 & \text{otherwise} \end{cases} )]