정수론 Chapter 9.1 - The order of an Integer and Primitive Roots
이 글의 내용은 성균관대학교 권순학 교수님의 2019년 5월 2일, 5월 7일 수업 내용을 재구성한 것입니다.
Definition: multiplicative order of \(a ; (\textrm{mod} ; m) \)
\(a^x \equiv 1 ; (\textrm{mod} ; m) \)을 만족하는 최소의 양수 \(x\)를 multiplicative order of \(a ; (\textrm{mod} ; m) \)라고 칭하고, \( x = ord_m a \)라고 나타낸다.
Remark: 위 조건을 만족하는 x는 항상 존재한다.
증명
$$ \because (a, m) = 1 $$
$$ \Rightarrow a^{\phi(m)} \equiv 1 ; (\textrm{mod} ; m) $$
$$ \Rightarrow ord_m a \le \phi(m) $$
예시: \( m = 5 \)
$$ ord_5 2 = 4 = \phi(5) $$
$$ ord_5 4 = 2 \lt \phi(5) $$
Theorem 9.1: \(a^x \equiv 1 ; (\textrm{mod} ; m) \Leftrightarrow ord_m a \mid x \)
$$ (a, m) = 1, m \ge 1 $$
\(\Leftarrow\) 증명
$$ x = (ord_m a) k, ;; k \in \mathbb{Z} $$
$$ a^x \equiv a^{(ord_m a) k} \equiv (a^{(ord_m a)})^k \equiv 1^k \equiv 1 ; (\textrm{mod} ; m) $$
\(\Rightarrow\) 증명
$$ x = (ord_m a) k + r ;; (0 \le r \lt ord_m a) $$
$$ 1 \equiv a^x \equiv a^{(ord_m a) k + r} \equiv a^{(ord_m a) k} a^r \equiv 1^k a^r \equiv a^r $$
$$ \Rightarrow r = 0 ;; (\because (ord_m a) \textrm{ is least positive integer satisfying } a^k \equiv 1) $$
Colorary 9.1.1: \( ord_m a \mid \phi(m) \)
$$ (a, m) = 1, ;; m \ge 1 $$
증명
$$ a^{\phi(m)} \equiv 1 ; (\textrm{mod} ; m) $$
$$ \Rightarrow ord_m a \mid \phi(m) $$
Theorem 9.2: \(a^i \equiv a^j ; (\textrm{mod} ; m) \Leftrightarrow i \equiv j ; (\textrm{mod} ; ord_m a) \)
$$ (a, m) = 1, ; m \ge 1 $$
\(i, j\)는 임의의 정수이다.
증명
$$ a^i \equiv a^j ; (\textrm{mod} ; m) $$
$$ \Leftrightarrow m \mid a^i - a^j $$
$$ \Leftrightarrow m \mid a^i (a^{j-i} -1) $$
$$ \Leftrightarrow m \mid (a^{j-i} -1) ;; (\because (a, m) = 1) $$
$$ \Leftrightarrow (a^{j-i} -1) \equiv 1 ; (\textrm{mod} ; m) $$
$$ \Leftrightarrow ord_m a \mid i - j $$
$$ \Leftrightarrow i \equiv j ; (\textrm{mod} ; ord_m a) $$
Definition: Primitive root
$$ (a, m) = 1, m \ge 1 $$
$$ \phi(m) = ord_m a $$
일 때, \(a\)를 primitive root modulo \(m\) 이라고 한다.
예시: m = 5
$$ \phi(5) = 4 $$
$$ ord_5 2 = 4 $$
이므로 \(2\)는 primitive root modulo \(5\)이다.
$$ ord_5 4 = 2 \neq \phi(5) $$
이므로 \(4\)는 primitive root modulo \(5\)가 아니다.
예시: m = 10
$$ \phi(10) = \phi(2)\phi(5) = 4 $$
$$ ord_{10} 3 = 4 $$
이므로 \(3\)은 primitive root modulo \(10\)이다.
Remark: Primitive root modulo \(n\)은 존재하지 않을 수도 있다
$$ n = 8 $$
$$ \phi(8) = 2^3 - 2^2 = 4 $$
$$ a = 1 ; (\textrm{mod} ; 8), a = 1 \\ a^2 = 1 ; (\textrm{mod} ; 8), a = 3, 5, 7 $$
$$ \therefore \textrm{no primitive root modulo } 8 $$
Theorem 9.3: \(a: \textrm{a primitive root modulo } n \Leftrightarrow \{a, a^2, \cdots, a^{\phi(n)} \} \) is RRS
$$ (a, n) = 1, n \ge 1 $$
\(\Leftarrow\) 증명
$$ a^{\phi(n)} \equiv 1 ; (\textrm{mod} ; n) $$
$$ a^j \not\equiv 1 ; (\textrm{mod} ; n) ;; (1 \le j \lt \phi(n)) $$
RRS이므로, 값이 전부 다르다
$$ ord_n a = \phi(n)) $$
\(\Rightarrow\) 증명
1. 모두 서로 다르다
$$ a^i \equiv a^j ; (\textrm{mod} ; n) $$
$$ \Leftrightarrow i \equiv j ; (\textrm{mod} ; ord_n a) ;; (\because \textrm{Thm 9.2}) $$
$$ ord_n a = \phi(n) ;; (\because \textrm{a is a primitive root modulo} ; n) $$
$$ \Leftrightarrow i \equiv j ; (\textrm{mod} ; \phi(n)) $$
$$ \Leftrightarrow \phi(n) \mid i - j $$
$$ 1 \le i, j \le \phi(n) \Rightarrow i = j $$
2. \( (a^j, n) =1 \)
$$ (a^j, n) = 1 = (a, n) $$
Remark: generator of RRS
\(a\)가 primitive root modulo \(n\)일 때, \(a\)를 RRS의 generator라고 부른다.
Theorem 9.4: \( ord_m (a^u) = \frac {ord_m a} {(ord_m a, u)} \)
$$ (a, m) = 1, m \ge 1 $$
증명
$$ t = ord_m a $$
$$ d = (t, u) $$
$$ t = dt_1, u = du_1 $$
$$ (t_1, u_1) = 1 $$
$$ s = ord_m (a^u) $$
\(s \mid t_1\)
$$ (a^u)^{t_1} \equiv a^{d u_1 t_1} \equiv (a^t)^{u_1} \equiv 1^{u_1} \equiv 1 $$
$$ \Rightarrow ord_m (a^u) \mid t_1 $$
$$ \Rightarrow s \mid t_1 $$
\(t_1 \mid s\)
$$ 1 \equiv (a^u)^s \equiv a^us ; (\textrm{mod} ; m) $$
$$ \Rightarrow ord_m a \mid us $$
$$ \Rightarrow t \mid us $$
$$ \Rightarrow dt_1 \mid d u_1 s $$
$$ \Rightarrow t_1 \mid u_1 s $$
$$ \Rightarrow t_1 \mid s ;; (\because (t_1, u_1) = 1) $$
Collorary 9.4.1: \(a^u: \textrm{a primitive root modulo } m \Leftrightarrow (u, \phi(m)) = 1 \)
증명
$$ \phi(m) = ord_m {a^u} ;; (\because a^u \textrm{ is a primitive root}) $$
$$ ord_m {a^u} = \frac {ord_m {a}} {(ord_m {a}, u)} $$
Theorem 9.5: \(n\)이 Primitive root를 가질 경우, 그 개수는 \(\phi(\phi(n))\)이다
증명
$$ r: \textrm{primitive root} ; (\textrm{mod} ; m) $$
$$ \{ r, r^2, \cdots, r^{\phi(m)} \} \textrm{: RRS} ; (\textrm{mod} m) $$
$$ \forall r^{j} \textrm{( in the RRS) has order of } r^j ; (\textrm{mod} ; m) $$
$$ ord_m r^j = \frac {ord_m r} {(j, ord_m r)} = \frac {\phi(m)} {(j, \phi(m))} ;; \because \textrm{Thm 9.4} $$
\(r^j\)이 Primitive root modulo \(m \Leftrightarrow (j, \phi(m)) = 1\)
$$ \{1, 2, \cdots, \phi(m)\}: \textrm{CRS} (\textrm{ mod } m) $$
$$ \phi(\phi(m)) = \textrm{the number of primitive roots} $$
Remark: \(p: \textrm{prime}\)
Primitive root \(\textrm{mod} ; p\)가 존재할 때, Primitive root의 개수는 \(\phi(\phi(m)) = \phi(p - 1)\)이다.
에시: \(p = 11\)
$$ \phi(\phi(11)) = \phi(10) = 4 $$
$$ g: \textrm{primitive root} $$
$$ \{g^1, g^3, g^7, g^9\}: \textrm{all primitive roots} \\ \because (1, 10) = (3, 10) = (7, 10) = (9, 10) = 1 $$
2는 primitive root modulo 11이다.
$$ 2^5 \equiv -1 ; (\textrm{mod} ; 11) \Rightarrow ord_{11} 2 = 10 $$
$$ \because ord_{11} 2 \mid 10 = \phi(11) $$
$$ {2^1, 2^3, 2^7, 2^9} \equiv \{2, 8, 7, 6\}:\textrm{all primitive roots} $$