정수론 #8 :: 원시 근 (Primitive root)

정의

1. the order of a mod n is the smallest k such that a^k ≡ 1 mod n

    a^k ≡ 1 mod n을 만족하는 가장 작은 k를 order of a mod n이라고 한다.

 

$\begin{gather*}ord_na=k, \ \ \ \ (ord_na \leq\phi(n)) \end{gather*}$

 

2. a is a primitive root mod n ↔

 

$\begin{gather*}ord_na=\phi(n) \end{gather*}$

 

  를 만족한다면 a는 mod n의 원시 근이다.

 

3. a is a primitive root mod p (prime) ↔

 

$\begin{gather*}ord_pa = p-1 \end{gather*}$

 

  를 만족한다면 a는 mod p의 원시 근이다.

 

• 원시근은 n보다 작은 숫자.
• gcd(a, n) ≠ 1 ⇒ a^k !≡ 1 이므로 n과 서로소인 a만 생각하자.
• n에 따라서 원시근이 없을 수도 있다.

 

---

 

Lemma 2

$\begin{gather*}t=ord_na \ \ is \ \ a \ \ divisor \ \ of \ \ \phi(n) \end{gather*}$

 

증명

 

$\begin{gather*}\phi(n)=tk+r, \ \ \ \ (0\leq r < t) \end{gather*}$

 

만약 φ(n)이 t로 나누어지지 않는다고 가정하면

 

$\begin{gather*}1≡a^{\phi(n)}≡a^{tk+r}=(a^t)^ka^r≡1^ka^r=a^r \\ \Rightarrow a^r≡1 \mod n \end{gather*}$

 

이때 t = ord_n a의 정의에 의하여 r ≠ 0 이면

 

$\begin{gather*}r\geq t \end{gather*}$

 

이어야 한다. t는 a^?≡1 mod n을 만족하는 가장 작은 수이기 때문이다.

하지만 r은 나머지이므로 t보다 작아야만 한다. 즉, 모순이다.

따라서 r = 0 이어야 한다. 나머지가 없다.

 

$\begin{gather*}\therefore \phi(n) = tk \\ \Rightarrow t|\phi(n) \end{gather*}$

 

그러므로 t는 φ(n)을 나눌 수 있다.

 

---

 

a가 mod n의 원시근이라면

$\begin{gather*}a, a^2,a^3,...,a^{\phi(n)} \mod n \end{gather*}$

위의 φ(n)개의 원소들은 전부 n과 서로소이다.

 

---

 

Lemma 3.

1 ≤ i ≤ j ≤ ord_n(a)이라면 a^i ≡ a^j mod n ⇔ i = j.

 

증명

a^i ≡ a^j mod n if and only if a^{j - i} ≡ 1 mod n.

 

이때 0 ≤ j - i < ord_n(a)인데, order보다 작으면서 0보다 큰 j - i라는 새로운 order가 존재한다는 것은 모순이다.

따라서 j - i = 0이다.

 

---

 

Question

1. 모든 n은 원시근을 가지는가?

⇒  X, ex) n=8 원시근 X

2. 원시근이 있다면 유일한가?

⇒  X, ex) n=5 원시근 2, 3 두 개 존재.

 

3. 어떤 n이 원시근을 가질까?

4. n의 원시근의 개수는?

⇒ prime에 대해서만 알아보자.

 

---

 

Theorem

Theorem 6. 모든 prime p는 원시근을 가진다.

Theorem 9. 원시근의 개수는 φ(p-1)개

 

$\begin{gather*}2,4,p^l,2p^l \end{gather*}$

1. 위와 같은 수들은 원시근을 가진다. (이때 p는 odd prime)
2. 개수로는 φ(φ(n))개를 가진다.

$\begin{gather*}a, a^2, ...,a^k,...,a^{\phi(n)} \end{gather*}$

들 중, primitive root of n은

$\begin{gather*}\Leftrightarrow \gcd(k, \phi(n))=1 \end{gather*}$

을 만족해야 한다.

$\begin{gather*}\Rightarrow \phi(\phi(n)) \end{gather*}$

ex) n = 13

$\begin{gather*}\phi(13)=12 \\ \phi(\phi(13)) = 4\\ \Leftrightarrow \gcd(k, 12) = 1 \end{gather*}$

이때 서로소인 k = 1, 5, 7, 11
또한 primitvie root 중 하나는 2
따라서 primitive root는 2^1, 2^5, 2^7, 2^11이다.

 

---

 

primitive root 찾기

먼저 primitvie root를 하나 찾고 그것의 power승 중에 p - 1과 서로소인 애들이 나머지 primitive root이다.

 

---

 

Lemma 7.

ord_n(a)=d라고 가정하자. 그렇다면

 

1. a^t ≡ 1 ⇔ d|t

 

증명

a^t ≡ 1이라고 가정하자. t = qd + r (0 ≤ r < t)

그러면 

 

$\begin{gather*}1 ≡ a^t = a^{qd+r}=(a^d)^q \cdot a^r ≡ a^r \end{gather*}$

 

이때 ord_n(a) = d 이므로 r = 0이다.

따라서 order는 t를 나눌 수 있다.

 

2. ord_n(a^k) = d if and only if gcd(k, d) = 1

 

증명

gcd(k, d) = 1이라고 가정하자. 그러면

 

$\begin{gather*}(a^k)^t ≡ 1 \Rightarrow a^{kt} ≡ 1 \Rightarrow d|kt \Rightarrow d|t \end{gather*}$

 

따라서 ord_n(a^k) = d.

 

반대로 ord_n(a^k) = d라고 가정해 보자. 이때 gcd(k, d) = g라고 한다면

 

$\begin{gather*}(a^k)^{\frac{d}{g}} = (a^d)^{\frac{k}{g}} ≡ 1 \end{gather*}$

 

This shows d/g ≥ d and so g = 1.

 

---

 

Corollary 11.

If d|(p-1), then x^d - 1 ≡ 0 has exactly d incongruent roots modulo p.

d가 p-1의 약수라면 ⇒ x^d - 1 ≡ 0 mod p는 정확히 d개의 해를 가진다.

 

증명

p-1 = de라고 하자. 그러면 페르마 소정리에 의하여

 

$\begin{gather*}x^{p-1} - 1 = (x^d - 1)(x^{d(e-1)}+x^{d(e-2)}+... +x^d +1) \end{gather*}$

 

x^{p-1} -1은 정확히 p-1의 해를 가진다.

이때 x^d - 1 은 최대 d개의 해를, 오른쪽 항은 최대 d(e-1)개의 해를 가질 수 있으나,

합쳐서 정확히 p-1개의 해를 만들어야 하므로 둘 다 최대로 해를 가져야만 한다.

 

따라서 x^d - 1 ≡ 0 mod p는 정확히 d개의 해를 가진다.

 

---

 

Lemma 12.

For any positive integer n,

 

$\begin{gather*}\sum_{d|n}\phi(d)=n \end{gather*}$

 

증명

For each divisor d of n, let

 

$\begin{gather*}C_d=\{ 1 \leq k \leq n \ \ : \ \ \gcd(k, n) =d \} \end{gather*}$

 

⇒ 최대 공약수가 d인 집합 (gcd(n, k) = d)

 

n = 18일 때를 예로 들어보자.

이때 I_n은 1 ≤ . ≤ n에서 n과 서로소인 수들의 집합이다. (gcd(n, k) = 1)

 

$\begin{gather*} C_1 = \{ 1, 5, 7, 11, 13, 17 \} = I_{18} \\ C_2 = \{ 2, 4, 8, 10, 14, 16 \} = 2I_{9} \\ C_3 = \{ 3, 15 \} = 3I_{6} \\ C_6 = \{ 6, 12 \} = 6I_{3} \\ C_9 = \{ 9 \} = 9I_{2} \\ C_{18} = \{ 18 \} = 18I_{1} \\ \end{gather*}$

 

As can be observed in this example,

 

$\begin{gather*} \sum_{d|n}\sharp(C_d) = n \ \ \ \ and \ \ \ \ C_d=d \cdot I_{\frac{n}{d}} \end{gather*}$

 

이때 #()은 원소의 개수를 의미한다.

C_d의 원소의 개수는 I_(n/d)의 원소의 개수와 같다.

 

Hence,

 

$\begin{gather*} \sharp(C_d) = \sharp(I_{\frac{n}{d}}) = \phi(\frac{n}{d}) \end{gather*}$

 

Therefore,

 

$\begin{gather*} \sum_{d|n}\phi(d)=\sum_{d|n}\phi(\frac{n}{d})=\sum_{d|n}\sharp(C_d)=n \end{gather*}$

 

---

 

Theorem 13.

For each divisor d of φ(p) = p - 1,

there are precisely φ(d) integers of order d which are incongruent to each other modulo p.

 

For p = 19, check:

 

2 → 4 → 8 → 16 → 13 → 7 → 14 → 9 → 18 → 17 → 15 → 11 → 3 → 6 → 12 → 5 → 10 → 1 (a mod 19)

 

d	d=1	d=2	d=3	d=6	d=9	d=18
a mod p	1	17	7, 11	8, 12	4, 16, 9, 17, 6, 5	2, 3, 10, 13, 14, 15
a	2^18	2^9	2^6, 2^12	2^3, 2^15	2^2, 2^4, 2^8, 2^10, 2^14, 2^16	2^1, 2^13, 2^17, 2^5, 2^7, 2^12

 

d는 p-1의 약수이다. 

a는 (원시 근중에 하나, 여기선 2로 고정.)^{(d와 서로소인 값) * n/d}. (ord_p(a) = d, n = p-1)

이때 d와 서로소인 값이 여러 개라면 a도 여러 개가 나온다.

 

증명

For each d, let

 

$\begin{gather*} F(d) := \sharp\{1 \leq a \leq p-1 \ \ : \ \ ord_p(a) = d \} \end{gather*}$

 

d가 p-1의 약수가 아니라면 F(d) = 0이다.

d가 p-1의 약수라면 페르마 소정리에 의하여 

 

$\begin{gather*} \sum_{d|(p-1)}F(d)=p-1 \end{gather*}$

 

If there is a number a of order d, the numbers a, a^2, ..., a^d are the roots of the equation x^d ≡ 1 mod p.

Furthermore, they are incongruent to each other by Lemma 3.

Hence these are all the roots of x^d ≡ 1 mod p.

 

Recall that a^k has order d if and only if gcd(k, d) = 1. Hence there are φ(d) numbers (of the form a^k) of order d.

Therefore,

 

$\begin{gather*} either \ \ F(d)=0 \ \ or \ \ F(d)=\phi(d) \end{gather*}$

 

한편, Lemma 12.

 

$\begin{gather*}\sum_{d|p-1}\phi(d)=p-1 \end{gather*}$

 

에 의하여 d|(p-1)이라면 F(d) = φ(d)이다.

 

In particular, there are φ(p-1) integers of order p-1 modulo p, all of which are primitive roots of p. (Theorem 6.)

 

Therefore, the "group" Z_p* = {1, 2, ..., p-1} under the multiplication mod p "isomorphic" to the group Z_{p-1} under the addition mod p.

 

$\begin{gather*} \mathbb{Z}_{m} = \{0, 1, 2, ..., m-1\} \\ \mathbb{Z}_m^* = \{1 \leq a \leq m |\gcd(a,m)=1\} \end{gather*}$

Complete residue system 완전잉여계 (Z_m, +) : Abelian group
Z_m는 m으로 나눈 나머지들의 집합이다.

Z_m와 그 집합에서의 덧셈 연산이 결합법칙, 항등원의 존재, 역원의 존재를 만족시키므로 위의 구조는 군(group)이다.
이때 교환법칙도 만족하므로 아벨 군이다.

역원이 존재하지 않을 수 있으므로, Z_m에선 곱셈 연산이 성립하지 않는다.

그러나 Z_p (p is prime.)에서는 원소들이 전부 p와 서로소 관계에 있다.
따라서 곱셈의 역원이 존재하므로 곱셈 연산이 성립한다. 사칙연산이 정의되므로 Z_p는 체(Field)이다.

Reduced residue system 기약잉여계 (Z_m*, *) : Abelian group
Z_m*는 gcd(a, m)=1을 만족하는 원소 a를 가지는 집합이다.

Z_m*에서는 곱셈 연산이 성립한다.
집합 내부 원소에 0이 존재하지 않는 등의 이유로 덧셈 연산은 성립하지 않는다.

 

Z_p* 와 Z_p-1 은 동형(isomorphic)이다.

예를 들어 p = 11에 대해 아래와 같은 1-1 대응이 존재한다.

 

$\begin{gather*} \mathbb{Z}_{11}^* \cong \mathbb{Z}_{10} \\ (\{1,2,3,4,5,6,7,8,9,10\}, * \mod 11) \leftrightarrow (\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}, + \mod 10) \end{gather*}$

 

따라서 다음과 같은 계산이 가능하다.

 

$\begin{gather*} 8*9 ≡ 2^3 * 2^6 \mod 11 \\ \Rightarrow 3 + 6 = 9 \\ \Rightarrow 2^9 ≡ 6 \mod 11 \end{gather*}$

 

Z_p*에서의 계산은 동형인 Z_p-1으로 보내서 덧셈 계산을 한 뒤 다시 Z_p*의 원소로 되돌리면 된다.

 

---

 

1/p를 사용하여 ord 계산

$\begin{gather*} \frac{1}{p}=\frac{?}{10^k-1} \\ \Rightarrow 10^k-1 = p*(?) \\ \Rightarrow 10^k \equiv 1 \mod p \end{gather*}$

 

이때 prime이므로 k는 최대 p-1 (⇒ 그럼 최소는 당연히 order)

k = 분자 등장숫자의 개수

 

Ex) p = 37

 

$\begin{gather*} \frac{1}{37}=0.027027...=\frac{027}{999}=\frac{027}{10^3-1} \\ \Rightarrow 10^3 \equiv1 \mod 37 \end{gather*}$

 

---

 

순환 군