원시근

수론에서, 양의 정수 $n$ 에 대한 원시근(原始根, 영어: primitive root)은 다음 조건을 만족시키는 정수 $g$ 이다.

만약 정수 $a$ 가 $n$ 과 서로소라면, $a$ 는 $g$ 의 거듭제곱과 법 $n$ 에 대하여 합동이다. 즉, $a \equiv g^{k} (\mod n)$ 인 음이 아닌 정수 $k$ 가 존재한다.

제곱수나 −1이 아닌 정수가 항상 무한히 많은 소수에 대한 원시근인지 여부는 알려져 있지 않다. 이를 아르틴 원시근 추측(영어: Artin’s primitive root conjecture)이라고 한다. 일반화 리만 가설은 아르틴 원시근 추측을 함의한다. 아르틴 원시근 추측의 반례 가운데 소수인 것은 2개 이하이며, 제곱 인수가 없는 반례는 3개 이하이다. 그러나 아르틴 원시근 추측을 만족시키는 명시적인 정수는 하나도 알려져 있지 않다.

정의

$n$ 이 양의 정수라고 하자.

$ℤ / (n)$ 은 정수환 $ℤ$ 의 주 아이디얼 $(n)$ 에 대한 몫환이다. $(ℤ / (n))^{\times}$ 는 $ℤ / (n)$ 의 가역원군이며, 그 크기는 $ϕ (n)$ 이다. (여기서 $ϕ$ 는 오일러 피 함수다.) $(ℤ / (n))^{\times}$ 이 순환군일 필요충분조건은

n = 1, 2, 4, p^{k}, 2 p^{k}

이다 ( $p$ 는 홀수 소수, $k$ 는 양의 정수). 즉, 만약 이 조건이 참이라면 $(ℤ / (n))^{\times}$ 을 생성하는 원소가 존재한다.

$\exp (ℤ / (n))^{\times}$ 가 군 $(ℤ / (n))^{\times}$ 의 지수라고 하자. (흔히 이를 카마이클 함수 $λ (n)$ 라고 한다.) $(ℤ / (n))^{\times}$ 은 유한 아벨 군이므로, 이는 $(ℤ / (n))^{\times}$ 의 원소의 최대 차수와 같다. 그렇다면, $\exp (ℤ / (n))^{\times}$ 는 $ϕ (n)$ 을 나누어떨어뜨리며, $(ℤ / (n))^{\times}$ 이 순환군일 필요충분조건은

\exp (ℤ / (n))^{\times} = ϕ (n)

이다. 2의 거듭제곱의 경우, 지수는 다음과 같다.

\exp (ℤ / (2^{k}))^{\times} = {\begin{matrix} ϕ (2^{k}) & k = 0, 1, 2 \\ ϕ (2^{k}) / 2 & k \geq 3 \end{matrix}

홀수 소수 $p$ 의 거듭제곱의 경우, $\exp (ℤ / (p^{k}))^{\times} = ϕ (p^{k})$ 이다. 나머지 경우는 항등식

\exp (ℤ / (p_{1}^{k_{1}} \dots p_{r}^{k_{r}}))^{\times} = lcm {\exp (ℤ / (p_{1}^{k_{1}}))^{\times}, \dots \exp (ℤ / (p_{r}^{k_{r}}))^{\times}}

을 통해서 구할 수 있다.

합동 산술의 언어를 사용하면, $ℤ / (n)$ 은 정수의 $n$ -합동류들의, (법 $n$ 에 대한) 덧셈과 곱셈에 대한 가환환이며, $(ℤ / (n))^{\times}$ 는 이 가운데 $n$ 과 서로소인 것들이 (법 $n$ 에 대한) 곱셈에 따라 이루는 아벨 군이다. 이 경우, 임의의 양의 정수 $n$ 및 정수 $g$ 에 대하여, 다음 조건들이 서로 동치이다.

$g$ 의 $n$ -합동류는 $(ℤ / (n))^{\times}$ 을 생성한다.
$n$ 과 서로소인 임의의 정수 $a$ 에 대하여, $a \equiv g^{k} (\mod n)$ 인 음이 아닌 정수 $k$ 가 존재한다.
$g^{ϕ (n)} \equiv 1 (\mod n)$ 이며, 모든 $d \in {1, 2, \dots, ϕ (n) - 1}$ 에 대하여 $g^{d} \equiv̸ 1 (\mod n)$ 이다.
$g$ 와 $n$ 은 서로소이며, $1, g, g^{2}, \dots, g^{ϕ (n) - 1}$ 은 서로 법 $n$ 에 대하여 합동이 아니다.
$g$ 와 $n$ 은 서로소이며, $g$ 의 합동류의 $(ℤ / (n))^{\times}$ 에서의 차수는 $ϕ (n)$ 이다.

만약 이 조건이 참이라면, $g$ 를 법 $n$ 에 대한 원시근(영어: primitive root modulo $n$ )이라고 한다.

물론, 법 $n$ 에 대한 원시근이 존재하려면 $n$ 은 위와 같은 특별한 꼴의 정수여야 한다. 주어진 양의 정수 $n$ 을 법으로 하였을 때, $g$ 가 원시근인지 여부는 물론 $g$ 의 합동류에만 의존한다. 그러나 많은 문제에서 법 $n$ 은 변한다.

성질

만약 $(ℤ / (n))^{\times}$ 이 순환군이라면, 그 생성 원소의 수는 $ϕ (ϕ (n))$ 이다.^[1]^{:212, Theorem 10.9} 즉, 만약 법 $n$ 에 대한 원시근이 존재한다면, 서로 합동이 아닌 원시근들의 수는 $ϕ (ϕ (n))$ 이다.

0은 법 1에 대한 원시근이다. 1은 법 2에 대한 원시근이다. 3은 법 4에 대한 원시근이다. 임의의 홀수 소수 $p$ 에 대하여, 모든

p, p^{2}, \dots, 2 p, 2 p^{2}, \dots

에 대한 공통의 원시근인 정수 $g (p)$ 가 존재한다.

제곱 잉여

임의의 홀수 소수 $p$ 및 법 $p$ 에 대한 원시근 $g$ 에 대하여, $g$ 로부터 유도되는 $ℤ / (p - 1)$ 의 덧셈군과 $(ℤ / (p))^{\times}$ 사이의 군 동형 사상

\log_{g} : (ℤ / (p))^{\times} \to ℤ / (p - 1)

을 생각하자. 그렇다면, 짝수의 원상은 $(ℤ / (p))^{\times}$ 의 어떤 원소의 제곱이며, 홀수의 원상은 $(ℤ / (p))^{\times}$ 의 원소의 제곱이 아니다. 즉, $g$ 의 짝수 제곱

1, g^{2}, g^{4}, \dots, g^{p - 1}

들은 법 $p$ 에 대한 제곱 잉여이며, 홀수 제곱

g, g^{3}, g^{5}, \dots, g^{p - 2}

들은 법 $p$ 에 대한 제곱 잉여가 아니다.

아르틴 원시근 추측

임의의 양의 정수 $h$ 에 대하여, 양의 실수

C (h) = \prod_{p ∤ h} (1 - \frac{1}{p (p - 1)}) \prod_{p ∣ h} (1 - \frac{1}{p - 1}) \in ℝ^{+}

를 생각하자. 여기서 $p$ 는 소수만을 취한다. 첫 번째 곱은 무한곱이며, 이는 항상 수렴한다. 두 번째 곱은 유한곱이다. 따라서 $C (h)$ 는 양의 실수이다. 특히, 만약 $h = 1$ 인 경우

C (1) = \prod_{p} (1 - \frac{1}{p (p - 1)}) = 0.3739558136192 \dots

는 아르틴 상수(영어: Artin constant)라고 한다 (OEIS의 수열 A005596).

임의의 정수 $g$ 에 대하여, 다음과 같은 데이터를 정의하자.

$P (g)$ 는 $g$ 가 법 $p$ 에 대한 원시근인 소수 $p$ 의 집합이다.
임의의 실수 $x$ 에 대하여, $P (g, x) = {p \in P (g) : p \leq x}$
$h (g)$ 는 $g = x^{h (g)}$ 인 정수 $x$ 가 존재하는 최대 정수다.

만약 일반화 리만 가설이 참이라면, 임의의 정수 $g$ 에 대하여, 다음 두 명제 역시 참이다.

(질적 아르틴 원시근 추측, 영어: Artin’s primitive root conjecture, qualitative form) 만약 $g \neq - 1$ 이며, $g$ 가 제곱수가 아니라면, $P (g)$ 는 무한 집합이다.
(양적 아르틴 원시근 추측, 영어: Artin’s primitive root conjecture, quantitative form) $# P (g, x) \approx C (h (g)) \frac{x}{\ln x} (x \to \infty)$

만약 $h (g)$ 가 홀수라면, $C (h (g))$ 는 아르틴 상수의 어떤 양의 유리수배이므로, 양적 추측은 질적 추측을 자명하게 함의한다. 만약 $h (g)$ 가 짝수라면, $C (h (g)) = 0$ 이며, $P (g)$ 는 자명하게 유한 집합이므로, 양적 추측은 자명하게 참이다.

질적·양적 아르틴 원시근 추측이 (무조건적으로) 참인지 여부는 열린 문제다. $P (g)$ 가 유한 집합인 소수 $g$ 는 2개 이하다. $P (g)$ 가 유한 집합인 제곱 인수가 없는 정수 $g$ 는 3개 이하다. 그러나, $P (g)$ 가 무한 집합인 명시적인 정수 $g$ 는 하나도 알려져 있지 않다.

참고 문헌

↑ Apostol, Tom Mike (1976). 《Introduction to analytic number theory》 (영어). Undergraduate Texts in Mathematics. 뉴욕: Springer-Verlag. doi:10.1007/978-1-4757-5579-4. ISBN 978-1-4419-2805-4. ISSN 0172-6056. MR 0434929. Zbl 0335.10001.

Moree, Pieter (2012). “Artin’s primitive root conjecture – a survey” (영어). Cojocaru, Alina; Gajda, Wojciec; Graves, Hester. 《Integers》 12 (6): 1305–1416. arXiv:math/0412262. doi:10.1515/integers-2012-0043. eISSN 1553-1732. MR 3011564. Zbl 1271.11002. </ref>

외부 링크

이철희. “원시근(primitive root)”. 《수학노트》.
이철희. “원시근에 대한 아틴의 추측”. 《수학노트》.
이철희. “소수에 대한 원시근(primitive root) 목록”. 《수학노트》.
“Primitive root” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Primitive root” (영어). 《Wolfram MathWorld》. Wolfram Research.
“Primitive root” (영어). 《PlanetMath》.
“properties of primitive roots” (영어). 《PlanetMath》.
“Definition: primitive root (number theory)” (영어). 《ProofWiki》.
“State of the art for primitive roots” (영어). 《Math Overflow》.

[Apostol-1] Apostol, Tom Mike (1976). 《Introduction to analytic number theory》 (영어). Undergraduate Texts in Mathematics. 뉴욕: Springer-Verlag. doi:10.1007/978-1-4757-5579-4. ISBN 978-1-4419-2805-4. ISSN 0172-6056. MR 0434929. Zbl 0335.10001.

[1]