# 정수론 Chapter 9.2 - Primitive Roots for Primes



이 글의 내용은 성균관대학교 권순학 교수님의 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개이다.

### 증명

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

<!-- 힌트는 p가 소수라는 점과 division algorithm이라고 한다. -->

### 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
$$