# 정수론 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} $$