원시근

개요 — 동기·문제의식

$\bmod p$ 에서 $a$ 의 거듭제곱 $a,a^2,a^3,\dots$ 을 차례로 계산하면 결국 $1$ 로 되돌아와 순환한다(페르마 소정리이 보장). 그런데 어떤 $a$ 는 순환 마디가 짧고(겨우 몇 개의 값만 도는), 어떤 $a$ 는 순환 마디가 가능한 한 길어서 0이 아닌 잉여류 전체($p-1$개)를 한 바퀴에 다 만들어낸다. 후자를 원시근(primitive root) 이라 부른다. 이것은 단순한 호기심이 아니라 구조적 사실의 표면이다 — $\mathbb{Z}_p^\times$(곱셈에 대한 $0$ 아닌 잉여류들의 군)가 순환군이라는, 정수론과 군론이 만나는 핵심 지점이다. 원시근을 하나 고정하면 곱셈이라는 다루기 힘든 연산을, 지수(지표)라는 덧셈으로 바꿀 수 있다 — 마치 로그가 곱셈을 덧셈으로 바꾸듯이. 이 아이디어는 다음 장의 이차잉여(QR ⟺ 짝수 지표)로 곧바로 이어지고, 암호학의 이산로그 문제(모듈러 거듭제곱과 RSA와 자매격인 Diffie–Hellman·ElGamal)의 기반이기도 하다.

직관

$\bmod p$ 의 0 아닌 잉여 $1,2,\dots,p-1$ 을 정점으로 하는 "곱셈의 시계"를 상상하자. $a$ 를 계속 곱하는 것은 이 시계 위에서 일정한 보폭으로 건너뛰는 것과 같다. 보폭이 시계의 칸 수($p-1$)와 서로소가 아니면 일부 칸만 밟고 제자리로 돌아오고(작은 위수), 서로소이면 — 즉 원시근이면 — 모든 칸을 정확히 한 번씩 밟고서야 출발점으로 돌아온다. 마치 시계 12칸을 5칸씩 건너뛰면($\gcd(5,12)=1$) 12개 칸을 다 거치지만, 4칸씩 건너뛰면($\gcd(4,12)=4$) 3개 칸만 도는 것과 같은 원리다. 원시근은 "가능한 가장 긴 순환"을 만드는 원소이고, 그 존재(모든 소수에 대해!)는 $\mathbb{Z}_p^\times$ 가 단순한 집합이 아니라 깔끔한 순환군 구조를 가진다는 깊은 사실을 반영한다.

정의

주의(편의상 정의의 미묘함): $\operatorname{ord}_m(a)$ 는 $\gcd(a,m)=1$ 일 때만 정의된다 — $\gcd(a,m)>1$ 이면 $a^k\equiv1$ 을 만족하는 $k$ 자체가 없다(예: $a$가 짝수, $m$도 짝수면 $a^k$ 도 짝수라 $1$ 이 될 수 없음). 지표는 밑 $g$ 의 선택에 의존하는 상대적인 양이지만, 일단 $g$ 를 고정하면 $\mathbb{Z}_p^\times$ 의 모든 원소에 유일한 지표가 부여된다 — $\{0,1,\dots,p-2\}$ 와 $\mathbb{Z}_p^\times$ 사이의 일대일 대응이다.

합성수 모듈러스: 원시근 개념은 $m$ 이 합성수일 때도 정의되지만(아래 정리), 일반적인 $\mathbb{Z}_m^\times$ 가 항상 순환군은 아니라는 점이 소수 모듈러스와의 결정적 차이다.

주요 정리

정리 (위수는 $\varphi$ 를 나눈다). $\gcd(a,m)=1$ 이면 $\operatorname{ord}_m(a)\mid\varphi(m)$; 특히 $\operatorname{ord}_p(a)\mid(p-1)$.²

정리 (원시근 정리, Primitive Root Theorem). 모든 소수 $p$ 는 원시근을 가진다. 더 정확히, $\bmod p$ 의 원시근은 정확히 $\varphi(p-1)$ 개 존재한다.³

정리 (원시근을 갖는 합성수의 분류). $m\ge2$ 가 원시근을 가짐 $\iff$ $m\in\{1,2,4,p^k,2p^k\}$ ($p$ 는 홀소수, $k\ge1$).⁴ 그 외의 모든 $m$(예: $8,12,15,16,\dots$ 또는 서로 다른 두 홀소수의 곱)은 $\mathbb{Z}_m^\times$ 가 순환군이 아니어서 원시근이 없다.

정리 (모든 거듭제곱의 위수 공식). $g$ 가 원시근이고 $\operatorname{ord}_p(g^k)$ 를 구하고 싶다면 $\operatorname{ord}_p(g^k)=\dfrac{p-1}{\gcd(k,p-1)}$. 따라서 $g^k$ 가 원시근 $\iff \gcd(k,p-1)=1$ — 이것이 원시근이 정확히 $\varphi(p-1)$ 개인 또 다른(생성적) 설명이다: 하나의 원시근 $g$ 로부터 $g^k$ ($1\le k\le p-1$, $\gcd(k,p-1)=1$) 가 나머지 전부를 만들어낸다.

정리 (지표 법칙). 원시근 $g$ 를 고정하면 $\operatorname{ind}_g(ab)\equiv\operatorname{ind}_g(a)+\operatorname{ind}_g(b)\pmod{p-1}$, $\operatorname{ind}_g(a^n)\equiv n\cdot\operatorname{ind}_g(a)\pmod{p-1}$.⁵ 즉 지표는 통상적인 로그 법칙을 그대로 따른다 — 곱셈 문제가 $\bmod(p-1)$ 덧셈 문제로 변환된다.

정리 (원시근과 이차잉여의 연결). $g$ 가 원시근이면, $a=g^k$ 가 $\bmod p$ 이차잉여 $\iff k$ 가 짝수.⁵ (이차잉여로 직결.)

원시근 찾기의 실용적 알고리즘과 한계. 원시근 정리는 존재만 보장할 뿐 구체적인 값을 주는 공식은 없다 — 표준 방법은 $a=2,3,5,6,\dots$ 순으로 시행착오로 확인하는 것뿐이다. 효율적으로 확인하려면, $p-1$ 의 모든 소인수 $q_1,\dots,q_r$ 을 구한 뒤 모든 $i$ 에 대해 $a^{(p-1)/q_i}\not\equiv1\pmod p$ 인지만 검사하면 충분하다(위수가 $p-1$ 의 진약수라면 어떤 $(p-1)/q_i$ 꼴에서 걸리기 때문). 이는 $p-1$ 개의 거듭제곱을 전부 계산하는 것보다 훨씬 빠르다.

미해결 문제 (Artin의 추측). 고정된 정수 $a$ (완전제곱이 아니고 $-1$ 도 아닌)에 대해, $a$ 가 원시근이 되는 소수 $p$ 가 무한히 많다는 추측은 아직 증명되지 않았다(예: $a=2$ 가 원시근인 소수가 무한히 많은가는 미해결).⁶ 원시근 정리가 "각 $p$ 마다 원시근이 존재한다"는 존재 정리인 데 반해, Artin의 추측은 "고정된 $a$ 가 얼마나 많은 $p$ 에서 원시근 노릇을 하는가"를 묻는 반대 방향의 질문이라는 점에서 흥미롭다.

예제

예제 1 (원시근 직접 검증, $\bmod7$). $3^1=3,\ 3^2=2,\ 3^3=6,\ 3^4=4,\ 3^5=5,\ 3^6=1$ — 여섯 개 거듭제곱이 $\{1,2,3,4,5,6\}$ 전체를 정확히 한 번씩 → $\operatorname{ord}_7(3)=6=\varphi(7)$ → $3$ 은 원시근. 반면 $2^1=2,2^2=4,2^3=1$ → 위수 $3$, 원시근 아님($\{1,2,4\}$만 순환).

예제 2 (원시근 개수 세기, $\bmod7$, $\bmod13$). $\bmod7$: $\varphi(6)=\varphi(2\cdot3)=1\cdot2=2$ → 원시근은 정확히 $2$ 개, 그것은 $3,5$. $\bmod13$: $\varphi(12)=\varphi(4)\varphi(3)=2\cdot2=4$ → 원시근은 $4$ 개. 실제로 $2^1,\dots,2^{12}\bmod13=2,4,8,3,6,12,11,9,5,10,7,1$ — 모든 값을 거치므로 $2$ 도 원시근. $\gcd(k,12)=1$ 인 $k\in\{1,5,7,11\}$ 에 대해 $2^k\bmod13=2,6,11,7$ — 네 원시근은 정확히 $\{2,6,7,11\}$.

예제 3 (모든 거듭제곱의 위수, $\bmod13$, $g=2$). $\operatorname{ord}_{13}(2^4)=\operatorname{ord}_{13}(16\bmod13=3)$. 공식: $\dfrac{12}{\gcd(4,12)}=\dfrac{12}{4}=3$. 검증: $3^1=3,3^2=9,3^3=27\equiv1$ → 정말 위수 $3$. ✓

예제 4 (지표표로 이산로그 풀기, $\bmod13$, $g=2$). $2$ 의 거듭제곱표: $k:1,2,3,4,5,6,7,8,9,10,11,12 \to 2^k\bmod13: 2,4,8,3,6,12,11,9,5,10,7,1$. 이걸 뒤집으면 $\operatorname{ind}_2(5)=9$ (표에서 $5$ 가 나오는 $k=9$). $2^x\equiv11\pmod{13}$ 을 풀려면 표에서 $11$ 을 찾으면 $k=7$ → $x=7$.

예제 5 (지표로 곱셈 문제 풀기). $\bmod13$, $g=2$. $\operatorname{ind}_2(5)=9,\ \operatorname{ind}_2(8)=3$ (표에서 $k=3$). $5\cdot8=40\equiv1\pmod{13}$ 을 지표로 검산: $\operatorname{ind}_2(5\cdot8)\equiv\operatorname{ind}_2(5)+\operatorname{ind}_2(8)=9+3=12\equiv0\pmod{12}$ → $\operatorname{ind}_2(1)=0$ (표 확인: $2^{12}\equiv1$, 관례상 지표 $0$ 또는 $12$, $\bmod12$ 로 둘 다 $0$). 일치 ✓.

예제 6 (이차잉여와 지표의 연결, $\bmod13$). $g=2$ 가 원시근. $a=5$: $\operatorname{ind}_2(5)=9$(홀수) → $5$ 는 QNR. $a=4$: $\operatorname{ind}_2(4)=2$(짝수) → $4$ 는 QR(확인: $2^2=4$). $a=12\equiv-1$: $\operatorname{ind}_2(12)=6$(짝수) → $-1$ 은 QR mod 13 — 이차잉여의 보충법칙 "$-1$ 은 $p\equiv1\pmod4$일 때만 QR"과 일치($13\equiv1\bmod4$).

예제 7 (원시근 후보 거르기 — 완전제곱은 절대 원시근이 아님). $a=b^2$ 형태이면 $a^{(p-1)/2}=b^{p-1}\equiv1\pmod p$(Fermat), 즉 위수가 $(p-1)/2$ 를 넘지 못한다 — 따라서 완전제곱 잉여는 결코 원시근이 될 수 없다. $\bmod11$: $4=2^2$ → 원시근 후보에서 즉시 제외 가능(실제로 $4$ 의 위수는 $5$).

예제 8 (응용 — 원시근으로 $x^k\equiv a$ 풀이 가능성 판정). $x^3\equiv5\pmod{13}$ 이 풀리는가? $g=2$, $\operatorname{ind}_2(5)=9$. $x=g^y$ 라 하면 $3y\equiv9\pmod{12}$. $\gcd(3,12)=3$ 이 $9$ 를 나누므로 해가 존재(정확히 $3$ 개): $y\equiv3\pmod4$ → $y=3,7,11$ → $x=2^3=8,\ 2^7=11,\ 2^{11}=7$. 검산: $8^3=512=39\cdot13+5\equiv5$ ✓.

흔한 오해와 함정

• "원시근은 항상 작은 수다" — 틀림. 가장 작은 원시근이 클 수도 있다(통계적으로 작은 경우가 많을 뿐, 보장은 없다). 후보를 $2,3,5,\dots$ 순서로 시행착오로 찾는 것이 표준 방법이지만 일반적인 빠른 공식은 없다.
• "완전제곱수는 가끔 원시근이 될 수 있다" — 틀림. 위 예제 7에서 보였듯 $a=b^2$ 꼴은 위수가 최대 $(p-1)/2$ 이므로 $p>3$ 인 한 절대 원시근이 아니다.
• "모든 $m$ 에 원시근이 있다" — 틀림. $m=8,12,15,16,20,\dots$ 등 분류 정리에 없는 합성수는 원시근이 없다. 예: $\bmod8$ 에서 $1,3,5,7$ 모두 $a^2\equiv1$ 이므로 위수는 $1$ 또는 $2$ 뿐, $\varphi(8)=4$ 에 도달 불가.
• "원시근이 유일하다" — 틀림. $\varphi(p-1)$ 개 존재(보통 여러 개). 다만 $p=3$ 처럼 작을 때만 유일할 수 있다.
• 지표를 절대적인 양으로 착각 — 지표는 밑 $g$ 의 선택에 의존하는 상대적 수치다. 다른 원시근을 밑으로 잡으면 같은 $a$ 라도 지표 값이 달라진다(다만 지표가 짝수인지 홀수인지는, $\gcd(2,p-1)$ 조건 하에서 밑과 무관하게 QR 여부를 결정한다).
• 위수 나눗셈 정리의 방향 혼동 — $\operatorname{ord}_m(a)\mid\varphi(m)$ 이지 그 역(($\varphi(m)$의 모든 약수가 실제로 어떤 원소의 위수다)은 항상 자명하지 않다. 소수 모듈러스에서는 참(원시근 정리 증명의 핵심 보조정리)이지만 합성수에서는 더 미묘하다.

큰 그림 / 연결

원시근은 $\mathbb{Z}_p^\times$ 를 "보이지 않는 순환군"에서 "눈에 보이는 덧셈 구조($\mathbb{Z}_{p-1}$)"로 바꾸는 사전(dictionary) 역할을 한다. 직접적으로 이차잉여(QR ⟺ 짝수 지표, 이는 이차 상호법칙로 가는 길의 또 다른 입구)와 연결되고, 페르마 소정리·오일러 φ 함수와 정리 이 위수의 존재와 나눗셈성을 보장하는 토대다. 암호학적으로, 지표(이산로그)를 큰 소수 모듈러스에서 역으로 계산하는 문제(이산로그 문제)는 모듈러 거듭제곱과 RSA가 기대는 인수분해의 어려움과 평행한, Diffie–Hellman/ElGamal 암호의 안전성 기반이다. 추상대수 쪽에서는 "$\mathbb{Z}_p^\times$ 는 순환군이다"라는 사실 자체가 algebra 위키의 cyclic-groups·structure-of-zn이 다루는 유한체의 곱셈군 구조 정리의 특수한 경우이며, 더 일반적으로 모든 유한체의 0 아닌 원소들의 곱셈군이 순환군이라는 사실(체론)의 정수론적 그림자다.

연습문제

1. $\bmod11$ 에서 $2$ 의 위수를 구하고 원시근인지 판정하라.
2. $\bmod13$ 의 원시근을 모두 나열하라($2$ 가 원시근임은 이미 확인됨을 이용).
3. $\bmod17$ 에서 $3$ 이 원시근인지 직접 거듭제곱으로 확인하라.
4. $\bmod p$ 의 원시근 개수가 $\varphi(p-1)$ 임을, $g$ 가 하나 주어졌을 때의 생성적 논증으로 설명하라.
5. $g$ 가 $\bmod13$ 의 원시근이고 $\operatorname{ord}_{13}(g^k)=4$ 가 되는 $k$ ($1\le k\le12$) 를 모두 구하라.
6. $a$ 가 QR ⟺ $\operatorname{ind}_g(a)$ 짝수임을 보여라.
7. $49=7^2$ 가 $\bmod p$ ($p>7$, 홀소수) 원시근이 될 수 없는 이유를 설명하라.
8. $x^2\equiv9\pmod{13}$ 을 지표(이산로그) 방법으로 풀어라 ($g=2$, $\operatorname{ind}_2(9)=8$ 사용).

관련 개념

• 페르마 소정리 — 위수가 $p-1$ 을 나눔의 토대
• 오일러 φ 함수와 정리 — 위수가 $\varphi(m)$ 을 나눔, 원시근 개수 공식
• 이차잉여 — QR ⟺ 짝수 지표
• 이차 상호법칙 — 이차잉여 계산의 다음 단계
• 합동식 — 위수·지표가 사는 합동산술의 틀
• algebra 위키 cyclic-groups, structure-of-zn — $\mathbb{Z}_p^\times$ 순환군(온톨로지 same-concept/uses)