2.4 원시근 & 모듈러 군 구조 실전 예제 10선
원시근의 존재성, 위수(Order)의 성질, 그리고 모듈러 곱셈군 $(\mathbb{Z}/n\mathbb{Z})^\times$의 대수적 구조를 깊이 있게 탐구합니다.
Ex 1. 법 n에 대한 위수(Order)
문제: $\text{ord}_{13}(3)$의 값을 구하시오.
$\phi(13) = 12$이므로 위수는 12의 약수($1, 2, 3, 4, 6, 12$) 중 하나이다.
$3^1 \equiv 3$, $3^2 \equiv 9$, $3^3 \equiv 27 \equiv 1 \pmod{13}$
따라서 최소의 양의 정수 $k=3$이 존재하므로 $\text{ord}_{13}(3) = 3$.
(참고: 위수가 $\phi(13)$보다 작으므로 3은 원시근이 아니다.)
Ex 2. 원시근 확인 절차
문제: 2가 법 11의 원시근임을 보이시오.
$\phi(11) = 10$이다. 10의 소인수는 2와 5이므로, $2^{10/2} \not\equiv 1$ 및 $2^{10/5} \not\equiv 1 \pmod{11}$임을 확인하면 된다.
1) $2^2 = 4 \not\equiv 1 \pmod{11}$
2) $2^5 = 32 \equiv 10 \equiv -1 \not\equiv 1 \pmod{11}$
위수가 10의 진약수가 아니므로 반드시 10이어야 한다. $\therefore$ 2는 원시근이다.
Ex 3. 원시근의 개수 산출
문제: 법 17에 대한 원시근의 개수를 구하시오.
법 $n$에 원시근이 존재하면 그 개수는 $\phi(\phi(n))$개이다.
$\phi(17) = 16$ (17은 소수)
$\phi(16) = 16(1 - 1/2) = 8$
따라서 법 17에 대한 원시근은 총 8개 존재한다.
Ex 4. 위수의 변환 법칙
문제: $\text{ord}_n(a) = k$일 때, $\text{ord}_n(a^m) = k/\gcd(m, k)$ 임을 증명하시오.
$x = \text{ord}_n(a^m)$이라 하자. $(a^m)^x \equiv a^{mx} \equiv 1 \pmod n$ 이 성립하려면 $k \mid mx$여야 한다.
이는 $\frac{k}{\gcd(m,k)} \mid \frac{m}{\gcd(m,k)}x$ 와 동치이다.
$\gcd(\frac{k}{\gcd(m,k)}, \frac{m}{\gcd(m,k)}) = 1$ 이므로, $\frac{k}{\gcd(m,k)} \mid x$ 가 성립한다.
최소의 $x$는 $\frac{k}{\gcd(m,k)}$이다.
Ex 5. 비순환군 $(\mathbb{Z}/8\mathbb{Z})^\times$
문제: 법 8은 원시근을 갖지 않음을 증명하시오.
$(\mathbb{Z}/8\mathbb{Z})^\times = \{1, 3, 5, 7\}$ 이고 $\phi(8)=4$이다.
$1^2 \equiv 1, 3^2 \equiv 9 \equiv 1, 5^2 \equiv 25 \equiv 1, 7^2 \equiv 49 \equiv 1 \pmod 8$.
모든 원소의 위수가 최대 2이며, 위수가 4인 원소가 존재하지 않는다.
따라서 법 8은 순환군이 아니며 원시근이 존재하지 않는다. (구조: $C_2 \times C_2$)
Ex 6. 소수 법에 대한 해의 개수
문제: 소수 $p$에 대해 $x^d \equiv 1 \pmod p$ ($d \mid p-1$)의 해의 개수가 정확히 $d$개임을 보이시오.
라그랑주 정리에 의해 $n$차 합동식의 해는 최대 $n$개이다.
$p-1 = d \cdot k$라 하면, $x^{p-1}-1 = (x^d-1)(x^{d(k-1)} + \dots + 1)$이다.
페르마의 소정리에 의해 $x^{p-1}-1 \equiv 0$은 $p-1$개의 해를 갖는다.
만약 $x^d-1 \equiv 0$의 해가 $d$개보다 적다면, 전체 해의 개수가 $p-1$개가 될 수 없다.
따라서 해의 개수는 정확히 $d$개이다.
Ex 7. 원시근을 이용한 QR 판별
문제: $g$가 법 $p$의 원시근일 때, $a = g^k$가 이차잉여(QR)일 필요충분조건은 $k$가 짝수임을 보이시오.
$\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \equiv (g^k)^{(p-1)/2} \equiv (g^{(p-1)/2})^k \pmod p$
오일러 판정법에 의해 $g^{(p-1)/2} \equiv -1$이므로 (원시근의 정의상 $1$일 수 없음),
$\left( \frac{a}{p} \right) \equiv (-1)^k \pmod p$.
$\therefore$ $k$가 짝수면 $1$ (QR), 홀수면 $-1$ (QNR)이다.
Ex 8. 지수 계산
문제: 법 13의 원시근 2에 대해, $2^x \equiv 5 \pmod{13}$을 만족하는 $x$를 구하시오.
2의 거듭제곱 나열: $2^1=2, 2^2=4, 2^3=8, 2^4=16 \equiv 3, 2^5=6, 2^6=12 \equiv -1, \dots$
$2^9 = 2^6 \cdot 2^3 \equiv -1 \cdot 8 = -8 \equiv 5 \pmod{13}$
$\therefore x = 9$. (이 $x$를 $ind_2(5)$라고도 부른다.)
Ex 9. 모든 원소의 곱
문제: 법 $n$에 원시근 $g$가 존재할 때, 기약잉여계 모든 원소의 곱은 $\pmod n$으로 얼마인가?
원소들의 곱 $P \equiv g^1 \cdot g^2 \cdot \dots \cdot g^{\phi(n)} \equiv g^{\frac{\phi(n)(\phi(n)+1)}{2}} \pmod n$
$\phi(n)$이 짝수이므로($n>2$), 지수를 $k = \frac{\phi(n)}{2}(\phi(n)+1)$로 둔다.
$P \equiv (g^{\phi(n)/2})^{\phi(n)+1} \equiv (-1)^{\text{odd}} \equiv -1 \pmod n$.
이는 윌슨의 정리($ (p-1)! \equiv -1 \pmod p $)의 일반화된 형태이다.
Ex 10. 소수의 거듭제곱과 원시근
문제: $g$가 법 $p$의 원시근일 때, $g^{p-1} \not\equiv 1 \pmod{p^2}$ 이면 $g$는 법 $p^k$의 원시근임을 설명하시오.
$g$가 법 $p$의 원시근이면, 법 $p^2$에서의 위수는 $\phi(p)=p-1$ 또는 $\phi(p^2)=p(p-1)$이다.
조건 $g^{p-1} \not\equiv 1 \pmod{p^2}$은 위수가 $p-1$이 아님을 보장하므로 위수는 $p(p-1)$이 된다.
한번 $p^2$에서 원시근이 되면 수학적 귀납법에 의해 모든 $p^k$에서도 원시근이 됨이 알려져 있다.