원시근

1의 원시 거듭제곱근 수론에서, 양의 정수 n에 대한 **원시근**(原始根, primitive root)은 다음 조건을 만족시키는 정수 g이다. * 만약 정수 a가 n과 서로소라면, a는 g의 거듭제곱과 법 n에 대하여 합동이다. 즉, a\equiv g^k\pmod n인 음이 아닌 정수 k가 존재한다. 제곱수나 −1이 아닌 정수가 항상 무한히 많은 소수에 대한 원시근인지 여부는 알려져 있지 않다. 이를 **아르틴 원시근 추측**(Artin’s primitive root conjecture)이라고 한다. 일반화 리만 가설은 아르틴 원시근 추측을 함의한다. 아르틴 원시근 추측의 반례 가운데 소수인 것은 2개 이하이며, 제곱 인수가 없는 반례는 3개 이하이다. 그러나 아르틴 원시근 추측을 만족시키는 명시적인 정수는 하나도 알려져 있지 않다.
# 정의
n이 양의 정수라고 하자. \mathbb Z/(n)은 정수환 \mathbb Z의 주 아이디얼 (n)에 대한 몫환이다. (\mathbb Z/(n))^\times는 \mathbb Z/(n)의 가역원군이며, 그 크기는 \phi(n)이다. (여기서 \phi는 오일러 피 함수다.) (\mathbb Z/(n))^\times이 순환군일 필요충분조건은 :n=1,2,4,p^k,2p^k 이다 (p는 홀수 소수, k는 양의 정수). 즉, 만약 이 조건이 참이라면 (\mathbb Z/(n))^\times을 생성하는 원소가 존재한다. \exp(\mathbb Z/(n))^\times가 군 (\mathbb Z/(n))^\times의 지수라고 하자. (흔히 이를 **카마이클 함수** \lambda(n)라고 한다.) (\mathbb Z/(n))^\times은 유한 아벨 군이므로, 이는 (\mathbb Z/(n))^\times의 원소의 최대 차수와 같다. 그렇다면, \exp(\mathbb Z/(n))^\times는 \phi(n)을 나누어떨어뜨리며, (\mathbb Z/(n))^\times이 순환군일 필요충분조건은 :\exp(\mathbb Z/(n))^\times=\phi(n) 이다. 2의 거듭제곱의 경우, 지수는 다음과 같다. :\exp(\mathbb Z/(2^k))^\times=\begin{cases}\phi(2^k) & k=0,1,2 \\\ \phi(2^k)/2 & k\ge3\end{cases} 홀수 소수 p의 거듭제곱의 경우, \exp(\mathbb Z/(p^k))^\times=\phi(p^k)이다. 나머지 경우는 항등식 :\exp(\mathbb Z/(p_1^{k_1}\cdots p_r^{k_r}))^\times=\operatorname{lcm}\\{\exp(\mathbb Z/(p_1^{k_1}))^\times,\dots\exp(\mathbb Z/(p_r^{k_r}))^\times\\} 을 통해서 구할 수 있다. 합동 산술의 언어를 사용하면, \mathbb Z/(n)은 정수의 n-합동류들의, (법 n에 대한) 덧셈과 곱셈에 대한 가환환이며, (\mathbb Z/(n))^\times는 이 가운데 n과 서로소인 것들이 (법 n에 대한) 곱셈에 따라 이루는 아벨 군이다. 이 경우, 임의의 양의 정수 n 및 정수 g에 대하여, 다음 조건들이 서로 동치이다. * g의 n-합동류는 (\mathbb Z/(n))^\times을 생성한다. * n과 서로소인 임의의 정수 a에 대하여, a\equiv g^k\pmod n인 음이 아닌 정수 k가 존재한다. * g^{\phi(n)}\equiv1\pmod n이며, 모든 d\in\\{1,2,\dots,\phi(n)-1\\}에 대하여 g^d\not\equiv1\pmod n이다. * g와 n은 서로소이며, 1,g,g^2,\dots,g^{\phi(n)-1}은 서로 법 n에 대하여 합동이 아니다. * g와 n은 서로소이며, g의 합동류의 (\mathbb Z/(n))^\times에서의 차수는 \phi(n)이다. 만약 이 조건이 참이라면, g를 **법 n에 대한 원시근**(primitive root modulo n)이라고 한다. 물론, 법 n에 대한 원시근이 존재하려면 n은 위와 같은 특별한 꼴의 정수여야 한다. 주어진 양의 정수 n을 법으로 하였을 때, g가 원시근인지 여부는 물론 g의 합동류에만 의존한다. 그러나 많은 문제에서 법 n은 변한다.
# 성질
만약 (\mathbb Z/(n))^\times이 순환군이라면, 그 생성 원소의 수는 \phi(\phi(n))이다.issn=0172-6056212, Theorem 10.9 즉, 만약 법 n에 대한 원시근이 존재한다면, 서로 합동이 아닌 원시근들의 수는 \phi(\phi(n))이다. 0은 법 1에 대한 원시근이다. 1은 법 2에 대한 원시근이다. 3은 법 4에 대한 원시근이다. 임의의 홀수 소수 p에 대하여, 모든 :p,p^2,\dots,2p,2p^2,\dots 에 대한 공통의 원시근인 정수 g(p)가 존재한다.
## 제곱 잉여
임의의 홀수 소수 p 및 법 p에 대한 원시근 g에 대하여, g로부터 유도되는 \mathbb Z/(p-1)의 덧셈군과 (\mathbb Z/(p))^\times 사이의 군 동형 사상 :\log_g\colon\mathbb(\mathbb Z/(p))^\times\to\mathbb Z/(p-1) 을 생각하자. 그렇다면, 짝수의 원상은 (\mathbb Z/(p))^\times의 어떤 원소의 제곱이며, 홀수의 원상은 (\mathbb Z/(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\nmid h}\left(1-\frac1{p(p-1)}\right)\prod_{p\mid h}\left(1-\frac1{p-1}\right)\in\mathbb R^+ 를 생각하자. 여기서 p는 소수만을 취한다. 첫 번째 곱은 무한곱이며, 이는 항상 수렴한다. 두 번째 곱은 유한곱이다. 따라서 C(h)는 양의 실수이다. 특히, 만약 h=1인 경우 :C(1)=\prod_p\left(1-\frac1{p(p-1)}\right)=0.3739558136192\cdots 는 **아르틴 상수**(Artin constant)라고 한다 A005596. 임의의 정수 g에 대하여, 다음과 같은 데이터를 정의하자. * P(g)는 g가 법 p에 대한 원시근인 소수 p의 집합이다. * 임의의 실수 x에 대하여, P(g,x)=\\{p\in P(g)\colon p\le x\\} * h(g)는 g=x^{h(g)}인 정수 x가 존재하는 최대 정수다. 만약 일반화 리만 가설이 참이라면, 임의의 정수 g에 대하여, 다음 두 명제 역시 참이다. * (**질적 아르틴 원시근 추측**, Artin’s primitive root conjecture, qualitative form) 만약 g\ne-1이며, g가 제곱수가 아니라면, P(g)는 무한 집합이다. * (**양적 아르틴 원시근 추측**, Artin’s primitive root conjecture, quantitative form) \\#P(g,x)\approx C(h(g))\frac x{\ln x}\qquad(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는 하나도 알려져 있지 않다.