정수론 Chapter 9.2 - Primitive Roots for Primes

Page content

이 글의 내용은 성균관대학교 권순학 교수님의 2019년 5월 7일 수업 내용을 재구성한 것입니다.

Theorem 9.6: Lagrange’s Theorem

$$ p: \textrm{prime} \\ f(x) = \sum_{i=0}^n {a_i x^i} ;; (a_i \in \mathbb{Z}) \\ a_n \not\equiv 0 ; (\textrm{mod} ; p) ;; ( \Leftrightarrow \deg(f) = n) $$

일 때,

$$ f(x) \equiv 0 ; (\textrm{mod} ; p) $$

의 incongruent한 해는 최대 n개이다.

증명

수업 시간에 생략하셨으므로 나중에 추가하겠다.

Remark: \(p\)가 소수가 아니면 9.6은 성립하지 않는다.

반례: \(f(x) = 2x + 4 ; (\textrm{mod} ; 6)\)

$$ x \equiv 1, 4 ; (\textrm{mod} ; 6) $$

반례: \(f(x) = x^2 - 1 ; (\textrm{mod} ; 15)\)

$$ x \equiv 1, 4, 11, 14; (\textrm{mod} ; 15) $$

Theorem 9.7: \(p\): prime, \(d \mid p - 1 \Rightarrow x^d \equiv 1 ; (\textrm{mod} ; p)\)의 해의 개수는 \(d\)

$$ d \ge 1 $$

증명

$$ p - 1 = de $$

$$ x^{p - 1} $$

$$ = x ^ {de} - 1 $$

$$ = (x^d - 1)(x^{d(e-1)} + x^{d(e-2)} + \cdots + x^d + 1) $$

$$ = (x^d - 1)g(x) $$

$$ S = \{x \mid x^{p-1} \equiv 1 ; (\textrm{mod} ; p)\} $$

$$ S_1 = \{x \mid x^{d} \equiv 1 ; (\textrm{mod} ; p)\} $$

$$ S_2 = \{x \mid g(x) = 0\} $$

$$ S = S_1 \cup S_2 \\ \mid S \mid \le \mid S_1 \mid + \mid S_2 \mid $$

$$ |S_1| \le d \\ |S_2| \le d(e - 1) $$

$$ |S| = p - 1 = |S_1| + |S_2| = d + d(e-1) = de $$

$$ \therefore |S_1| = d $$

Lemma 9.1: \((ord_p a, ord_p b) = 1 \Rightarrow ord_p {ab} = ord_p a ord_p b\)

증명

$$ s = ord_p a, ; t = ord_p b, ; u = ord_p {ab} $$

\(u \mid st\)

$$ (ab)^{st} = (a^s)^t (b^t)^s \equiv 1 ; (\textrm{mod} ; 1) $$

$$ \Rightarrow ord_p {ab} \mid st ;;;(\because \textrm{Thm 9.1}) $$

\(st \mid u\)

$$ 1 \equiv (ab)^u \equiv a^u b^u ; (\textrm{mod} ; p) $$

$$ a^u \equiv b^{-u} ; (\textrm{mod} ; p) \\ (\because a, b \in \textrm{RRS}, \textrm{inverse exists}) $$

$$ ord_p (a^u) = ord_p (b^{-u}) $$

$$ \Rightarrow \frac {ord_p a} {(ord_p a, u)} = \frac {ord_p b} {(ord_p b, -u)} = 1 $$

$$ \Rightarrow \\ (ord_p a, u) = ord_p a \Rightarrow ord_p a \mid u \\ (ord_p b, u) = ord_p b \Rightarrow ord_p b \mid u $$

Collorary 9.8.1: Every prime has a primitive root \((\text{ mod } p)\)

증명

$$ \exists ; g ;; \text{s.t. } \text{ord}_p g = p - 1 $$

임을 보이면 충분하다.

$$ \phi(p) = p - 1 = \prod_{i=1}^{n} q_i^{\mu_i} $$

$$ \forall i ; \exists a ;; \text{s.t. } \text{ord}_p a_i = q_i^{u_i} $$

Claim: \(q^{\mu}\)개의 해중 최소 1개는 \(q^{\mut}\)승을 취해줘야만 \(\equiv 1\)이 된다

$$ \Leftrightarrow \exists ; a \text{ s.t. } \begin{cases} a^{q^u} \equiv = 1 (\text{mod } p) \\ \text{ord}_pa = q^u \end{cases} $$

증명

명제가 거짓이라고 가정하자. 그러면

$$ \text{ord}_p a \lt q^{\mu} \\ \text{ord}_p a \mid q^{\mu} ; (\because \text{Thm 9.1}) \\ \Rightarrow \text{ord}_p a = q^s, s \le \mu - 1 $$

$$ a^{q^{\mu - 1}} \equiv 1 (\text{ mod } p) ;; (\because \text{ord}_p a \not= q^u) \\ \Rightarrow x^{q^{\mu}} \text{and } \Rightarrow x^{q^{\mu - 1}} \text{ has same solution} $$

해의 개수가 같을 수 없으므로 모순이다.

증명 마무리

$$ \Rightarrow \text{ord}_p {a_1 a_2 \cdots a_n} \\\ = \text{ord} a_1 \text{ord} a_2 \cdots \text{ord} a_n \\ = \prod_i q_i^{\mu_i} $$

$$ $$

Remark: Primitive root exists for \(p^m\)

$$ p: \text{odd prime} \\ m: \text{integer}, m \ge 1 $$

Remark: \(n\) has primitive root \(\Leftrightarrow n = 2, 4, p^m, 2p^m\)

$$ p: \text{odd prime} \\ m: \text{integer}, m \ge 1 $$