이 글의 내용은 성균관대학교 권순학 교수님의 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 \)라고 나타낸다.
증명
$$
\\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$이다.
$$
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)
$$
$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}
$$
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}
$$