원시근 문서 원본 보기

{{다른 뜻|1의 원시 거듭제곱근}}
[[수론]]에서, 양의 [[정수]] <math>n</math>에 대한 '''원시근'''(原始根, {{llang|en|primitive root}})은 다음 조건을 만족시키는 정수 <math>g</math>이다.
* 만약 정수 <math>a</math>가 <math>n</math>과 [[서로소 (수론)|서로소]]라면, <math>a</math>는 <math>g</math>의 거듭제곱과 법 <math>n</math>에 대하여 [[모듈러 산술|합동]]이다. 즉, <math>a\equiv g^k\pmod n</math>인 음이 아닌 정수 <math>k</math>가 존재한다.

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

== 정의 ==
<math>n</math>이 양의 정수라고 하자.

<math>\mathbb Z/(n)</math>은 [[정수환 (수학)|정수환]] <math>\mathbb Z</math>의 [[주 아이디얼]] <math>(n)</math>에 대한 [[몫환]]이다. <math>(\mathbb Z/(n))^\times</math>는 <math>\mathbb Z/(n)</math>의 [[가역원군]]이며, 그 크기는 <math>\phi(n)</math>이다. (여기서 <math>\phi</math>는 [[오일러 피 함수]]다.) <math>(\mathbb Z/(n))^\times</math>이 [[순환군]]일 [[필요충분조건]]은
:<math>n=1,2,4,p^k,2p^k</math>
이다 (<math>p</math>는 홀수 [[소수 (수론)|소수]], <math>k</math>는 양의 정수). 즉, 만약 이 조건이 참이라면 <math>(\mathbb Z/(n))^\times</math>을 생성하는 원소가 존재한다.

<math>\exp(\mathbb Z/(n))^\times</math>가 군 <math>(\mathbb Z/(n))^\times</math>의 [[군의 지수|지수]]라고 하자. (흔히 이를 '''[[카마이클 함수]]''' <math>\lambda(n)</math>라고 한다.) <math>(\mathbb Z/(n))^\times</math>은 [[유한군|유한]] [[아벨 군]]이므로, 이는 <math>(\mathbb Z/(n))^\times</math>의 원소의 최대 차수와 같다. 그렇다면, <math>\exp(\mathbb Z/(n))^\times</math>는 <math>\phi(n)</math>을 나누어떨어뜨리며, <math>(\mathbb Z/(n))^\times</math>이 [[순환군]]일 [[필요충분조건]]은
:<math>\exp(\mathbb Z/(n))^\times=\phi(n)</math>
이다. 2의 거듭제곱의 경우, 지수는 다음과 같다.
:<math>\exp(\mathbb Z/(2^k))^\times=\begin{cases}\phi(2^k) & k=0,1,2 \\ \phi(2^k)/2 & k\ge3\end{cases}</math>
홀수 소수 <math>p</math>의 거듭제곱의 경우, <math>\exp(\mathbb Z/(p^k))^\times=\phi(p^k)</math>이다. 나머지 경우는 항등식
:<math>\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\}</math>
을 통해서 구할 수 있다.

[[합동 산술]]의 언어를 사용하면, <math>\mathbb Z/(n)</math>은 정수의 <math>n</math>-[[합동류]]들의, (법 <math>n</math>에 대한) 덧셈과 곱셈에 대한 [[가환환]]이며, <math>(\mathbb Z/(n))^\times</math>는 이 가운데 <math>n</math>과 [[서로소 (수론)|서로소]]인 것들이 (법 <math>n</math>에 대한) 곱셈에 따라 이루는 [[아벨 군]]이다. 이 경우, 임의의 양의 정수 <math>n</math> 및 정수 <math>g</math>에 대하여, 다음 조건들이 서로 [[동치]]이다.
* <math>g</math>의 <math>n</math>-합동류는 <math>(\mathbb Z/(n))^\times</math>을 생성한다.
* <math>n</math>과 서로소인 임의의 정수 <math>a</math>에 대하여, <math>a\equiv g^k\pmod n</math>인 음이 아닌 정수 <math>k</math>가 존재한다.
* <math>g^{\phi(n)}\equiv1\pmod n</math>이며, 모든 <math>d\in\{1,2,\dots,\phi(n)-1\}</math>에 대하여 <math>g^d\not\equiv1\pmod n</math>이다.
* <math>g</math>와 <math>n</math>은 서로소이며, <math>1,g,g^2,\dots,g^{\phi(n)-1}</math>은 서로 법 <math>n</math>에 대하여 합동이 아니다.
* <math>g</math>와 <math>n</math>은 서로소이며, <math>g</math>의 합동류의 <math>(\mathbb Z/(n))^\times</math>에서의 차수는 <math>\phi(n)</math>이다.
만약 이 조건이 참이라면, <math>g</math>를 '''법 <math>n</math>에 대한 원시근'''({{llang|en|primitive root modulo <math>n</math>}})이라고 한다.

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

== 성질 ==
만약 <math>(\mathbb Z/(n))^\times</math>이 [[순환군]]이라면, 그 생성 원소의 수는 <math>\phi(\phi(n))</math>이다.<ref name="Apostol">{{서적 인용|성=Apostol|이름=Tom Mike|저자링크=톰 어포스톨|제목=Introduction to analytic number theory|언어=en|총서=Undergraduate Texts in Mathematics|출판사=Springer-Verlag|위치=[[뉴욕]]|날짜=1976|isbn=978-1-4419-2805-4|doi=10.1007/978-1-4757-5579-4|mr=0434929|zbl=0335.10001|issn=0172-6056}}</ref>{{rp|212, Theorem 10.9}} 즉, 만약 법 <math>n</math>에 대한 원시근이 존재한다면, 서로 합동이 아닌 원시근들의 수는 <math>\phi(\phi(n))</math>이다.

0은 법 1에 대한 원시근이다. 1은 법 2에 대한 원시근이다. 3은 법 4에 대한 원시근이다. 임의의 홀수 소수 <math>p</math>에 대하여, 모든
:<math>p,p^2,\dots,2p,2p^2,\dots</math>
에 대한 공통의 원시근인 정수 <math>g(p)</math>가 존재한다.

=== 제곱 잉여 ===
임의의 홀수 소수 <math>p</math> 및 법 <math>p</math>에 대한 원시근 <math>g</math>에 대하여, <math>g</math>로부터 유도되는 <math>\mathbb Z/(p-1)</math>의 덧셈군과 <math>(\mathbb Z/(p))^\times</math> 사이의 군 [[동형 사상]]
:<math>\log_g\colon\mathbb(\mathbb Z/(p))^\times\to\mathbb Z/(p-1)</math>
을 생각하자. 그렇다면, 짝수의 [[원상 (수학)|원상]]은 <math>(\mathbb Z/(p))^\times</math>의 어떤 원소의 제곱이며, 홀수의 [[원상 (수학)|원상]]은 <math>(\mathbb Z/(p))^\times</math>의 원소의 제곱이 아니다. 즉, <math>g</math>의 짝수 제곱
:<math>1,g^2,g^4,\dots,g^{p-1}</math>
들은 법 <math>p</math>에 대한 [[제곱 잉여]]이며, 홀수 제곱
:<math>g,g^3,g^5,\dots,g^{p-2}</math>
들은 법 <math>p</math>에 대한 제곱 잉여가 아니다.

=== 아르틴 원시근 추측 ===
임의의 양의 정수 <math>h</math>에 대하여, 양의 실수
:<math>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^+</math>
를 생각하자. 여기서 <math>p</math>는 소수만을 취한다. 첫 번째 곱은 [[무한곱]]이며, 이는 항상 [[수렴]]한다. 두 번째 곱은 유한곱이다. 따라서 <math>C(h)</math>는 양의 실수이다. 특히, 만약 <math>h=1</math>인 경우
:<math>C(1)=\prod_p\left(1-\frac1{p(p-1)}\right)=0.3739558136192\cdots</math>
는 '''아르틴 상수'''({{llang|en|Artin constant}})라고 한다 {{OEIS|A005596}}.

임의의 정수 <math>g</math>에 대하여, 다음과 같은 데이터를 정의하자.
* <math>P(g)</math>는 <math>g</math>가 법 <math>p</math>에 대한 원시근인 소수 <math>p</math>의 집합이다.
* 임의의 [[실수]] <math>x</math>에 대하여, <math>P(g,x)=\{p\in P(g)\colon p\le x\}</math>
* <math>h(g)</math>는 <math>g=x^{h(g)}</math>인 정수 <math>x</math>가 존재하는 최대 정수다.

만약 [[일반화 리만 가설]]이 참이라면, 임의의 정수 <math>g</math>에 대하여, 다음 두 명제 역시 참이다.
* ('''질적 아르틴 원시근 추측''', {{llang|en|Artin’s primitive root conjecture, qualitative form}}) 만약 <math>g\ne-1</math>이며, <math>g</math>가 [[제곱수]]가 아니라면, <math>P(g)</math>는 [[무한 집합]]이다.
* ('''양적 아르틴 원시근 추측''', {{llang|en|Artin’s primitive root conjecture, quantitative form}}) <math display="block">\#P(g,x)\approx C(h(g))\frac x{\ln x}\qquad(x\to\infty)</math>
만약 <math>h(g)</math>가 홀수라면, <math>C(h(g))</math>는 아르틴 상수의 어떤 양의 유리수배이므로, 양적 추측은 질적 추측을 자명하게 함의한다. 만약 <math>h(g)</math>가 짝수라면, <math>C(h(g))=0</math>이며, <math>P(g)</math>는 자명하게 [[유한 집합]]이므로, 양적 추측은 자명하게 참이다.

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

== 참고 문헌 ==
<references/>
* {{저널 인용|성=Moree|이름=Pieter|기타=Cojocaru, Alina; Gajda, Wojciec; Graves, Hester|제목=Artin’s primitive root conjecture – a survey|언어=en|저널=Integers|권=12|호=6|쪽=1305–1416|날짜=2012|eissn=1553-1732|doi=10.1515/integers-2012-0043|mr=3011564|zbl=1271.11002|arxiv=math/0412262}}</ref>

== 외부 링크 ==
* {{수학노트|제목=원시근(primitive root)}}
* {{수학노트|제목=원시근에 대한 아틴의 추측}}
* {{수학노트|제목=소수에 대한 원시근(primitive root) 목록}}
* {{eom|제목=Primitive root}}
* {{매스월드|id=PrimitiveRoot|제목=Primitive root}}
* {{플래닛매스|urlname=primitiveroot|제목=Primitive root}}
* {{플래닛매스|urlname=propertiesofprimitiveroots|제목=properties of primitive roots}}
* {{proofwiki|id=Definition:Primitive Root (Number Theory)|제목=Definition: primitive root (number theory)}}
* {{웹 인용|url=https://mathoverflow.net/questions/428755/state-of-the-art-for-primitive-roots|제목=State of the art for primitive roots|웹사이트=Math Overflow|언어=en}}

{{위키데이터 속성 추적}}
{{새 사용자 작업에서 제외 (링크 추가)}}

[[분류:모듈러 산술]]