位数と原始根 | 初等整数論

1 位数の定義と基本性質

定義 1.1 (位数). $m$ を正整数、 $a$ を $\gcd(a,m)=1$ を満たす整数とする。 $a^k\equiv1\pmod m$ を満たす最小の正整数 $k$ を、 $a$ の法 $m$ に関する位数 (multiplicative order) といい、 $\operatorname{ord}_m(a)$ と書く。

$m\ge2$ の場合、§A4.7 定理 2.2により $a^{\varphi(m)}\equiv1\pmod m$ が成り立ちます。 $m=1$ の場合にも、§A4.7 注意 2.3により同じ合同式が成り立ちます。したがって、 $a^k\equiv1\pmod m$ を満たす正整数 $k$ が存在し、その最小値を取ることができます。法 $1$ では $a\equiv1\pmod1$ なので、任意の整数 $a$ の位数は $1$ です。

命題 1.2. $m$ を正整数、 $a$ を $\gcd(a,m)=1$ を満たす整数とする。任意の正整数 $n$ について

a^n\equiv1\pmod m\quad\Longleftrightarrow\quad\operatorname{ord}_m(a)\mid n

が成り立つ。

証明. $d=\operatorname{ord}_m(a)$ とおく。 $d\mid n$ ならば、正整数 $q$ を用いて $n=dq$ と書くことができるので、 $a^n=(a^d)^q\equiv1\pmod m$ である。

$a^n\equiv1\pmod m$ とする。 $n=qd+r$ 、 $0\le r<d$ と書くと、

a^n=(a^d)^q a^r\equiv a^r\pmod m

より $a^r\equiv1\pmod m$ である。 $r>0$ ならば、 $d$ より小さい正整数 $r$ が $a^r\equiv1\pmod m$ を満たし、 $d$ の最小性に反する。したがって $r=0$ であり、 $d\mid n$ である。▨

系 1.3. $m$ を正整数、 $a$ を $\gcd(a,m)=1$ を満たす整数とする。このとき $\operatorname{ord}_m(a)\mid\varphi(m)$ である。

証明. $m\ge2$ ならば§A4.7 定理 2.2により、 $m=1$ ならば§A4.7 注意 2.3により、 $a^{\varphi(m)}\equiv1\pmod m$ である。命題 1.2を $n=\varphi(m)$ に適用すると、 $\operatorname{ord}_m(a)\mid\varphi(m)$ を得る。▨

位数を求めるときには、 $\varphi(m)$ の正の約数を候補として調べます。

命題 1.4. $m$ を正整数、 $a$ を $\gcd(a,m)=1$ を満たす整数とし、 $d=\operatorname{ord}_m(a)$ とおく。任意の正整数 $k$ について

\operatorname{ord}_m(a^k)=\frac{d}{\gcd(d,k)}

が成り立つ。

証明. $h=\gcd(d,k)$ とし、 $d=hd'$ 、 $k=hk'$ と書くと、 $\gcd(d',k')=1$ である。 $kd'=k'd$ なので、 $(a^k)^{d'}=(a^d)^{k'}\equiv1\pmod m$ である。

正整数 $r$ が $(a^k)^r\equiv1\pmod m$ を満たすとする。命題 1.2により $d\mid kr$ なので、 $d'\mid k'r$ である。§A4.3 補題 1.1により $ud'+vk'=1$ を満たす整数 $u,v$ を取ると、

r=ud'r+vk'r

の右辺の両項は $d'$ で割り切れる。したがって $d'\mid r$ であり、 $r\ge d'$ である。よって、 $(a^k)^r\equiv1\pmod m$ を満たす最小の正整数 $r$ は $d'=d/h$ である。▨

2 原始根とそのべき

定義 2.1 (原始根). $m$ を正整数とする。整数 $g$ が $\gcd(g,m)=1$ かつ $\operatorname{ord}_m(g)=\varphi(m)$ を満たすとき、 $g$ を法 $m$ の原始根 (primitive root) という。

系 2.2. $m$ を正整数、 $g$ を法 $m$ の原始根とする。 $g,g^2,\ldots,g^{\varphi(m)}$ は、 $m$ と互いに素な剰余類を一つずつ尽くす。任意の正整数 $k$ について、 $g^k$ が法 $m$ の原始根であるための必要十分条件は $\gcd(k,\varphi(m))=1$ である。したがって、法 $m$ の原始根の剰余類は

g^k\pmod m\qquad\bigl(1\le k\le\varphi(m),\ \gcd(k,\varphi(m))=1\bigr)

で尽くされ、その個数は $\varphi(\varphi(m))$ である。

証明. $1\le i<j\le\varphi(m)$ とし、 $g^i\equiv g^j\pmod m$ と仮定する。 $g^i$ は $m$ と互いに素なので、§A4.5 命題 3.2により $g^{j-i}\equiv1\pmod m$ である。 $0<j-i<\varphi(m)=\operatorname{ord}_m(g)$ なので、位数の最小性に反する。よって $g,g^2,\ldots,g^{\varphi(m)}$ は法 $m$ で互いに異なる。各べきは $m$ と互いに素であり、そのような剰余類は $\varphi(m)$ 個なので、この列がすべてを尽くす。

命題 1.4により、任意の正整数 $k$ について

\operatorname{ord}_m(g^k)=\frac{\varphi(m)}{\gcd(k,\varphi(m))}

である。したがって、 $g^k$ が原始根であることと $\gcd(k,\varphi(m))=1$ は同値である。 $1\le k\le\varphi(m)$ の範囲にそのような $k$ は $\varphi(\varphi(m))$ 個あり、対応するべきは法 $m$ で互いに異なるので、原始根の個数も $\varphi(\varphi(m))$ である。▨

3 素数を法とする原始根の存在

素数を法とする原始根が存在することの証明には、多項式の合同式の解の個数を用います。

補題 3.1. $p$ を素数、 $f(X)$ を次数 $d\ge0$ の整数係数多項式とし、その最高次係数は $p$ で割り切れないとする。合同式 $f(x)\equiv0\pmod p$ の解の剰余類は高々 $d$ 個である。

証明. $d=0$ のとき、 $f$ は $p$ で割り切れない定数なので、解はない。 $d\ge1$ とし、次数 $d-1$ の場合には主張が成り立つと仮定する。 $f(x)\equiv0\pmod p$ に解がなければ主張は成り立つので、解の一つを $a$ とする。各正整数 $j$ について

X^j-a^j=(X-a)\sum_{\ell=0}^{j-1}X^{j-1-\ell}a^\ell

であるから、整数係数多項式 $g(X)$ を用いて

f(X)-f(a)=(X-a)g(X)

と書くことができる。 $g$ の次数は $d-1$ であり、最高次係数は $f$ と等しい。 $a$ と合同でない解 $b$ について

0\equiv f(b)-f(a)=(b-a)g(b)\pmod p

である。 $p\nmid b-a$ なので、§A4.2 補題 2.1により $p\mid g(b)$ である。帰納法の仮定により、そのような $b$ の剰余類は高々 $d-1$ 個である。 $a$ の剰余類を加えても、 $f$ の解は高々 $d$ 個である。▨

定理 3.2. $p$ を素数とする。このとき法 $p$ の原始根が存在する。

証明. $p-1$ の各正の約数 $d$ について、 $1,2,\ldots,p-1$ のうち法 $p$ に関する位数が $d$ である整数の個数を $e_d$ とする。合同式 $x^d\equiv1\pmod p$ の解の剰余類の集合を $R_d$ とする。多項式 $X^d-1$ の次数は $d$ であり、最高次係数は $1$ なので、補題 3.1により $R_d$ の元は高々 $d$ 個である。

$e_d>0$ と仮定し、法 $p$ に関する位数が $d$ である整数 $a$ を $1\le a\le p-1$ の範囲に取る。 $1\le i<j\le d$ について $a^i\equiv a^j\pmod p$ ならば、§A4.5 命題 3.2により $a^{j-i}\equiv1\pmod p$ となり、 $0<j-i<d$ は位数の最小性に反する。したがって、 $a,a^2,\ldots,a^d$ は法 $p$ で互いに異なる。また、 $(a^i)^d=(a^d)^i\equiv1\pmod p$ なので、その $d$ 個の剰余類はすべて $R_d$ に属する。 $R_d$ の元は高々 $d$ 個なので、 $a,a^2,\ldots,a^d$ が $R_d$ を尽くす。

位数が $d$ である整数は $x^d\equiv1\pmod p$ を満たすので、その剰余類は $R_d$ に属する。命題 1.4により、 $1\le i\le d$ の範囲で $a^i$ の位数が $d$ であることと、 $\gcd(i,d)=1$ は同値である。そのような $i$ は $\varphi(d)$ 個なので、 $e_d=\varphi(d)$ である。 $e_d=0$ の場合と合わせると、各正の約数 $d$ について $e_d$ は $0$ または $\varphi(d)$ に等しく、特に $e_d\le\varphi(d)$ である。

§A4.8 命題 2.1より $\varphi(p)=p-1$ であり、系 1.3より $1,2,\ldots,p-1$ の各整数の位数は $p-1$ の正の約数である。これらの整数を位数によって分けて数えると

\sum_{d\mid p-1}e_d=p-1

である。一方、§A4.8 命題 5.1を正整数 $p-1$ に適用すると

\sum_{d\mid p-1}\varphi(d)=p-1

である。いずれの和も $p-1$ の正の約数にわたる和である。各項で $e_d\le\varphi(d)$ であり、両方の総和が等しいので、すべての $d$ について $e_d=\varphi(d)$ である。実際、一つでも $e_d<\varphi(d)$ となる約数があれば、 $\sum e_d<\sum\varphi(d)$ となり、二つの総和が等しいことに反する。特に $e_{p-1}=\varphi(p-1)\ge1$ なので、位数が $p-1=\varphi(p)$ である整数が存在する。この整数は法 $p$ の原始根である。▨

例 3.3. 法 $7$ に関する $3$ のべきの余りは

3^1\equiv3,\quad3^2\equiv2,\quad3^3\equiv6,\quad3^4\equiv4,\quad3^5\equiv5,\quad3^6\equiv1\pmod7

である。 $1,2,\ldots,6$ が一回ずつ現れ、位数は $6=\varphi(7)$ なので、 $3$ は法 $7$ の原始根である。系 2.2より、原始根は $\gcd(k,6)=1$ を満たす $k=1,5$ に対応するので、法 $7$ の原始根の剰余類は $3$ と $3^5\equiv5$ の二つである。

注意 3.4. 原始根が存在する法は、 $1,2,4,p^k,2p^k$ （ $p$ は奇素数、 $k\ge1$ ）の形のものに限られる。この分類の一般の証明はここでは示さない。法 $1$ では任意の整数の位数が $1=\varphi(1)$ なので、唯一の剰余類が原始根である。法 $2$ では $1$ の位数が $1=\varphi(2)$ なので、 $1$ が原始根である。

法 $8$ では $\varphi(8)=4$ であるが、 $8$ と互いに素な剰余類の代表 $1,3,5,7$ の平方はすべて

1^2\equiv3^2\equiv5^2\equiv7^2\equiv1\pmod8

である。命題 1.2より、それぞれの位数は $2$ の約数なので $1$ または $2$ であり、位数 $4$ の整数は存在しない。したがって、法 $8$ には原始根が存在しない。

4 例題

レベル3 — 位数と原始根

次の問いに答えよ。ord_p(a) は $a^k$ $\equiv$ 1 (mod p) を満たす最小の正整数 k（a の法 p における位数）を表す。

解法の型ord_p(a) は必ず p−1 の約数（オイラーの定理＋除法の原理）。ord_p(a) $=$ p−1 のとき a は原始根で、原始根の個数は $\phi(p-1)$

例 4.1. 法 7 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/7\mathbb{Z})^{\times} : \operatorname{ord}_{7}(a) = 6 \,\} = ?

答 $2$

注意 (Z/7Z)* は位数 6 の巡回群なので、生成元（＝原始根）の個数は $\phi(6) =$ 2。原始根 g を1つ取れば $g^i$ が原始根 $\Leftrightarrow$ gcd(i, 6) $=$ 1 だから、その個数はちょうど $\phi(6)$ 個になる。実際 1 $\le$ a $\le$ 6 の原始根は 3, 5 の 2 個。

例 4.2. 5 の法 19 における位数 ord_19(5) を求めよ。

\operatorname{ord}_{19}(5) = ?

答 $9$

注意位数は必ず $\phi(19) =$ 18 の約数（1, 2, 3, 6, 9, 18）なので、その候補だけ調べればよい。べきを順に計算すると 5^1 $\equiv$ 5、5^2 $\equiv$ 6、5^3 $\equiv$ 11、5^4 $\equiv$ 17、5^5 $\equiv$ 9、5^6 $\equiv$ 7、5^7 $\equiv$ 16、5^8 $\equiv$ 4、5^9 $\equiv$ 1 (mod 19) で、初めて 1 になるのは指数 9 のとき。よって ord_19(5) $=$ 9。

例 4.3. 8 の法 17 における位数 ord_17(8) を求めよ。

\operatorname{ord}_{17}(8) = ?

答 $8$

注意位数は必ず $\phi(17) =$ 16 の約数（1, 2, 4, 8, 16）なので、その候補だけ調べればよい。べきを順に計算すると 8^1 $\equiv$ 8、8^2 $\equiv$ 13、8^3 $\equiv$ 2、8^4 $\equiv$ 16、8^5 $\equiv$ 9、8^6 $\equiv$ 4、8^7 $\equiv$ 15、8^8 $\equiv$ 1 (mod 17) で、初めて 1 になるのは指数 8 のとき。よって ord_17(8) $=$ 8。

例 4.4. 3 は法 17 の原始根であるか判定せよ。

a = 3, \quad p = 17 : \quad a \text{ は法 } p \text{ の原始根か？}

答 $\operatorname{ord}_{17}(3) = 16 = 17 - 1 \quad \Rightarrow$ 原始根である

注意べきを順に計算すると 3^1 $\equiv$ 3、3^2 $\equiv$ 9、3^3 $\equiv$ 10、3^4 $\equiv$ 13、3^5 $\equiv$ 5、3^6 $\equiv$ 15、3^7 $\equiv$ 11、3^8 $\equiv$ 16、3^9 $\equiv$ 14、3^10 $\equiv$ 8、3^11 $\equiv$ 7、3^12 $\equiv$ 4、3^13 $\equiv$ 12、3^14 $\equiv$ 2、3^15 $\equiv$ 6、3^16 $\equiv$ 1 (mod 17) なので ord_17(3) $=$ 16。 $\phi(17) =$ 16 なので、位数が 16 いっぱいに達しており 3 は原始根（3 のべきが 1 から 16 をすべて1回ずつ尽くす）。

例 4.5. 16 の法 19 における位数 ord_19(16) を求めよ。

\operatorname{ord}_{19}(16) = ?

答 $9$

注意位数は必ず $\phi(19) =$ 18 の約数（1, 2, 3, 6, 9, 18）なので、その候補だけ調べればよい。べきを順に計算すると 16^1 $\equiv$ 16、16^2 $\equiv$ 9、16^3 $\equiv$ 11、16^4 $\equiv$ 5、16^5 $\equiv$ 4、16^6 $\equiv$ 7、16^7 $\equiv$ 17、16^8 $\equiv$ 6、16^9 $\equiv$ 1 (mod 19) で、初めて 1 になるのは指数 9 のとき。よって ord_19(16) $=$ 9。

例 4.6. 4 は法 13 の原始根であるか判定せよ。

a = 4, \quad p = 13 : \quad a \text{ は法 } p \text{ の原始根か？}

答 $\operatorname{ord}_{13}(4) = 6 \ne 12 \quad \Rightarrow$ 原始根でない

注意べきを順に計算すると 4^1 $\equiv$ 4、4^2 $\equiv$ 3、4^3 $\equiv$ 12、4^4 $\equiv$ 9、4^5 $\equiv$ 10、4^6 $\equiv$ 1 (mod 13) なので ord_13(4) $=$ 6。 $\phi(13) =$ 12 なので、位数 6 は 12 の真の約数にとどまり、4 のべきは 6 個の値しか取らない。よって原始根ではない。

例 4.7. 2 は法 17 の原始根であるか判定せよ。

a = 2, \quad p = 17 : \quad a \text{ は法 } p \text{ の原始根か？}

答 $\operatorname{ord}_{17}(2) = 8 \ne 16 \quad \Rightarrow$ 原始根でない

注意べきを順に計算すると 2^1 $\equiv$ 2、2^2 $\equiv$ 4、2^3 $\equiv$ 8、2^4 $\equiv$ 16、2^5 $\equiv$ 15、2^6 $\equiv$ 13、2^7 $\equiv$ 9、2^8 $\equiv$ 1 (mod 17) なので ord_17(2) $=$ 8。 $\phi(17) =$ 16 なので、位数 8 は 16 の真の約数にとどまり、2 のべきは 8 個の値しか取らない。よって原始根ではない。

例 4.8. 8 の法 11 における位数 ord_11(8) を求めよ。

\operatorname{ord}_{11}(8) = ?

答 $10$

注意位数は必ず $\phi(11) =$ 10 の約数（1, 2, 5, 10）なので、その候補だけ調べればよい。べきを順に計算すると 8^1 $\equiv$ 8、8^2 $\equiv$ 9、8^3 $\equiv$ 6、8^4 $\equiv$ 4、8^5 $\equiv$ 10、8^6 $\equiv$ 3、8^7 $\equiv$ 2、8^8 $\equiv$ 5、8^9 $\equiv$ 7、8^10 $\equiv$ 1 (mod 11) で、初めて 1 になるのは指数 10 のとき。よって ord_11(8) $=$ 10（位数が p−1 に等しいので 8 は法 11 の原始根）。

例 4.9. 法 11 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/11\mathbb{Z})^{\times} : \operatorname{ord}_{11}(a) = 10 \,\} = ?

答 $4$

注意 (Z/11Z)* は位数 10 の巡回群なので、生成元（＝原始根）の個数は $\phi(10) =$ 4。原始根 g を1つ取れば $g^i$ が原始根 $\Leftrightarrow$ gcd(i, 10) $=$ 1 だから、その個数はちょうど $\phi(10)$ 個になる。実際 1 $\le$ a $\le$ 10 の原始根は 2, 6, 7, 8 の 4 個。

例 4.10. 3 の法 7 における位数 ord_7(3) を求めよ。

\operatorname{ord}_{7}(3) = ?

答 $6$

注意位数は必ず $\phi(7) =$ 6 の約数（1, 2, 3, 6）なので、その候補だけ調べればよい。べきを順に計算すると 3^1 $\equiv$ 3、3^2 $\equiv$ 2、3^3 $\equiv$ 6、3^4 $\equiv$ 4、3^5 $\equiv$ 5、3^6 $\equiv$ 1 (mod 7) で、初めて 1 になるのは指数 6 のとき。よって ord_7(3) $=$ 6（位数が p−1 に等しいので 3 は法 7 の原始根）。

5 演習

レベル3 — 位数と原始根

次の問いに答えよ。ord_p(a) は $a^k$ $\equiv$ 1 (mod p) を満たす最小の正整数 k（a の法 p における位数）を表す。

解法の型ord_p(a) は必ず p−1 の約数（オイラーの定理＋除法の原理）。ord_p(a) $=$ p−1 のとき a は原始根で、原始根の個数は $\phi(p-1)$

問題 5.1. 12 は法 13 の原始根であるか判定せよ。

a = 12, \quad p = 13 : \quad a \text{ は法 } p \text{ の原始根か？}

解答.

答 $\operatorname{ord}_{13}(12) = 2 \ne 12 \quad \Rightarrow$ 原始根でない

注意べきを順に計算すると 12^1 $\equiv$ 12、12^2 $\equiv$ 1 (mod 13) なので ord_13(12) $=$ 2。 $\phi(13) =$ 12 なので、位数 2 は 12 の真の約数にとどまり、12 のべきは 2 個の値しか取らない。よって原始根ではない。▨

問題 5.2. 法 11 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/11\mathbb{Z})^{\times} : \operatorname{ord}_{11}(a) = 10 \,\} = ?

解答.

答 $4$

問題 5.3. 法 19 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/19\mathbb{Z})^{\times} : \operatorname{ord}_{19}(a) = 18 \,\} = ?

解答.

答 $6$

注意 (Z/19Z)* は位数 18 の巡回群なので、生成元（＝原始根）の個数は $\phi(18) =$ 6。原始根 g を1つ取れば $g^i$ が原始根 $\Leftrightarrow$ gcd(i, 18) $=$ 1 だから、その個数はちょうど $\phi(18)$ 個になる。実際 1 $\le$ a $\le$ 18 の原始根は 2, 3, 10, 13, 14, 15 の 6 個。▨

問題 5.4. 15 は法 17 の原始根であるか判定せよ。

a = 15, \quad p = 17 : \quad a \text{ は法 } p \text{ の原始根か？}

解答.

答 $\operatorname{ord}_{17}(15) = 8 \ne 16 \quad \Rightarrow$ 原始根でない

注意べきを順に計算すると 15^1 $\equiv$ 15、15^2 $\equiv$ 4、15^3 $\equiv$ 9、15^4 $\equiv$ 16、15^5 $\equiv$ 2、15^6 $\equiv$ 13、15^7 $\equiv$ 8、15^8 $\equiv$ 1 (mod 17) なので ord_17(15) $=$ 8。 $\phi(17) =$ 16 なので、位数 8 は 16 の真の約数にとどまり、15 のべきは 8 個の値しか取らない。よって原始根ではない。▨

問題 5.5. 18 は法 19 の原始根であるか判定せよ。

a = 18, \quad p = 19 : \quad a \text{ は法 } p \text{ の原始根か？}

解答.

答 $\operatorname{ord}_{19}(18) = 2 \ne 18 \quad \Rightarrow$ 原始根でない

注意べきを順に計算すると 18^1 $\equiv$ 18、18^2 $\equiv$ 1 (mod 19) なので ord_19(18) $=$ 2。 $\phi(19) =$ 18 なので、位数 2 は 18 の真の約数にとどまり、18 のべきは 2 個の値しか取らない。よって原始根ではない。▨

問題 5.6. 法 17 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/17\mathbb{Z})^{\times} : \operatorname{ord}_{17}(a) = 16 \,\} = ?

解答.

答 $8$

注意 (Z/17Z)* は位数 16 の巡回群なので、生成元（＝原始根）の個数は $\phi(16) =$ 8。原始根 g を1つ取れば $g^i$ が原始根 $\Leftrightarrow$ gcd(i, 16) $=$ 1 だから、その個数はちょうど $\phi(16)$ 個になる。実際 1 $\le$ a $\le$ 16 の原始根は 3, 5, 6, 7, 10, 11, 12, 14 の 8 個。▨

問題 5.7. 9 の法 17 における位数 ord_17(9) を求めよ。

\operatorname{ord}_{17}(9) = ?

解答.

答 $8$

注意位数は必ず $\phi(17) =$ 16 の約数（1, 2, 4, 8, 16）なので、その候補だけ調べればよい。べきを順に計算すると 9^1 $\equiv$ 9、9^2 $\equiv$ 13、9^3 $\equiv$ 15、9^4 $\equiv$ 16、9^5 $\equiv$ 8、9^6 $\equiv$ 4、9^7 $\equiv$ 2、9^8 $\equiv$ 1 (mod 17) で、初めて 1 になるのは指数 8 のとき。よって ord_17(9) $=$ 8。▨

問題 5.8. 法 13 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/13\mathbb{Z})^{\times} : \operatorname{ord}_{13}(a) = 12 \,\} = ?

解答.

答 $4$

注意 (Z/13Z)* は位数 12 の巡回群なので、生成元（＝原始根）の個数は $\phi(12) =$ 4。原始根 g を1つ取れば $g^i$ が原始根 $\Leftrightarrow$ gcd(i, 12) $=$ 1 だから、その個数はちょうど $\phi(12)$ 個になる。実際 1 $\le$ a $\le$ 12 の原始根は 2, 6, 7, 11 の 4 個。▨

問題 5.9. 14 は法 19 の原始根であるか判定せよ。

a = 14, \quad p = 19 : \quad a \text{ は法 } p \text{ の原始根か？}

解答.

答 $\operatorname{ord}_{19}(14) = 18 = 19 - 1 \quad \Rightarrow$ 原始根である

注意べきを順に計算すると 14^1 $\equiv$ 14、14^2 $\equiv$ 6、14^3 $\equiv$ 8、14^4 $\equiv$ 17、14^5 $\equiv$ 10、14^6 $\equiv$ 7、14^7 $\equiv$ 3、14^8 $\equiv$ 4、14^9 $\equiv$ 18、14^10 $\equiv$ 5、14^11 $\equiv$ 13、14^12 $\equiv$ 11、14^13 $\equiv$ 2、14^14 $\equiv$ 9、14^15 $\equiv$ 12、14^16 $\equiv$ 16、14^17 $\equiv$ 15、14^18 $\equiv$ 1 (mod 19) なので ord_19(14) $=$ 18。 $\phi(19) =$ 18 なので、位数が 18 いっぱいに達しており 14 は原始根（14 のべきが 1 から 18 をすべて1回ずつ尽くす）。▨

問題 5.10. 5 の法 11 における位数 ord_11(5) を求めよ。

\operatorname{ord}_{11}(5) = ?

解答.

答 $5$

注意位数は必ず $\phi(11) =$ 10 の約数（1, 2, 5, 10）なので、その候補だけ調べればよい。べきを順に計算すると 5^1 $\equiv$ 5、5^2 $\equiv$ 3、5^3 $\equiv$ 4、5^4 $\equiv$ 9、5^5 $\equiv$ 1 (mod 11) で、初めて 1 になるのは指数 5 のとき。よって ord_11(5) $=$ 5。▨

問題 5.11. 7 は法 13 の原始根であるか判定せよ。

a = 7, \quad p = 13 : \quad a \text{ は法 } p \text{ の原始根か？}

解答.

答 $\operatorname{ord}_{13}(7) = 12 = 13 - 1 \quad \Rightarrow$ 原始根である

注意べきを順に計算すると 7^1 $\equiv$ 7、7^2 $\equiv$ 10、7^3 $\equiv$ 5、7^4 $\equiv$ 9、7^5 $\equiv$ 11、7^6 $\equiv$ 12、7^7 $\equiv$ 6、7^8 $\equiv$ 3、7^9 $\equiv$ 8、7^10 $\equiv$ 4、7^11 $\equiv$ 2、7^12 $\equiv$ 1 (mod 13) なので ord_13(7) $=$ 12。 $\phi(13) =$ 12 なので、位数が 12 いっぱいに達しており 7 は原始根（7 のべきが 1 から 12 をすべて1回ずつ尽くす）。▨

問題 5.12. 9 は法 11 の原始根であるか判定せよ。

a = 9, \quad p = 11 : \quad a \text{ は法 } p \text{ の原始根か？}

解答.

答 $\operatorname{ord}_{11}(9) = 5 \ne 10 \quad \Rightarrow$ 原始根でない

注意べきを順に計算すると 9^1 $\equiv$ 9、9^2 $\equiv$ 4、9^3 $\equiv$ 3、9^4 $\equiv$ 5、9^5 $\equiv$ 1 (mod 11) なので ord_11(9) $=$ 5。 $\phi(11) =$ 10 なので、位数 5 は 10 の真の約数にとどまり、9 のべきは 5 個の値しか取らない。よって原始根ではない。▨

問題 5.13. 16 の法 17 における位数 ord_17(16) を求めよ。

\operatorname{ord}_{17}(16) = ?

解答.

答 $2$

注意位数は必ず $\phi(17) =$ 16 の約数（1, 2, 4, 8, 16）なので、その候補だけ調べればよい。べきを順に計算すると 16^1 $\equiv$ 16、16^2 $\equiv$ 1 (mod 17) で、初めて 1 になるのは指数 2 のとき。よって ord_17(16) $=$ 2。▨

問題 5.14. 法 7 の原始根は全部でいくつあるか求めよ。

\#\{\, a \in (\mathbb{Z}/7\mathbb{Z})^{\times} : \operatorname{ord}_{7}(a) = 6 \,\} = ?

解答.

答 $2$

注意 (Z/7Z)* は位数 6 の巡回群なので、生成元（＝原始根）の個数は $\phi(6) =$ 2。原始根 g を1つ取れば $g^i$ が原始根 $\Leftrightarrow$ gcd(i, 6) $=$ 1 だから、その個数はちょうど $\phi(6)$ 個になる。実際 1 $\le$ a $\le$ 6 の原始根は 3, 5 の 2 個。▨

問題 5.15. 17 の法 19 における位数 ord_19(17) を求めよ。

\operatorname{ord}_{19}(17) = ?

解答.

答 $9$

注意位数は必ず $\phi(19) =$ 18 の約数（1, 2, 3, 6, 9, 18）なので、その候補だけ調べればよい。べきを順に計算すると 17^1 $\equiv$ 17、17^2 $\equiv$ 4、17^3 $\equiv$ 11、17^4 $\equiv$ 16、17^5 $\equiv$ 6、17^6 $\equiv$ 7、17^7 $\equiv$ 5、17^8 $\equiv$ 9、17^9 $\equiv$ 1 (mod 19) で、初めて 1 になるのは指数 9 のとき。よって ord_19(17) $=$ 9。▨

§A4.12位数と原始根

1 位数の定義と基本性質

2 原始根とそのべき

3 素数を法とする原始根の存在

4 例題

5 演習

前提記事