初等整数論/原始根と指数

原始根

フェルマーの小定理によると、素数 $p$ とそれに互いに素な数 $a$ について、$a^{p-1}\equiv 1{\pmod {p}}$ だった。

また位数の法則によれば、位数は $p-1$ の約数だった。そこで、位数が $p-1$ になる数 $a$ を、「$p$ （を法として）の原始根」という。

例えば、$2^{3}\equiv 1{\pmod {7}}$ なので、2 は 7 の原始根ではない。

$3^{1}\equiv 3,3^{2}\equiv 2,3^{3}\equiv 6{\pmod {7}}$ なので、3 は 7 を法としての原始根である。（位数の法則より位数の可能性のあるものは 7-1 = 6 の約数、1, 2, 3, 6）

さて、原始根が存在することを証明しなければならない。$a$ を $p$ で割り切れない任意の数とする。$a$ の位数を $e$ とおく。すなわち、$a^{0},a^{1},a^{2},\cdots ,a^{e-1}\not \equiv 1{\pmod {p}}\cdots (1)$ である。

位数に関する命題より合同方程式 $X^{e}\equiv 1{\pmod {p}}\cdots (2)$ の解は $a^{0}\equiv 1,a^{1},a^{2},\cdots ,a^{e-1}$ で尽くされる。

さて、$e=p-1$ ならば証明は終了する。また位数の法則によって、$e\leqq p-1$ だから、$e<p-1$ であったとしよう。そうすると、$p$ で割ったときの余りは $p$ 種類なのだから、(1) のどれとも合同でない数 $b$ が存在する。また、特にこのとき、$e<p-1$ なので、$p$ で割り切れないような $b$ が取ってこれる。もちろん $b$ は定め方から (2) の解とはなり得ない。したがって、位数を $f$ とおいて、$b^{f}\equiv 1{\pmod {p}}$ とすると、 $f$ は $e$ の約数たりえない。もちろん、$f>1$ である。

ここで、次のようにして $ab$ の位数は $a$ の位数より大きいことが示される。

(i) $(e,f)=1$ のとき

$ab^{ef}=a^{ef}b^{ef}=(a^{e})^{f}(b^{f})^{e}\equiv 1{\pmod {p}}$

$(ab)^{x}\equiv 1{\pmod {p}}$ とすれば、

$(ab)^{ex}\equiv 1$ より $b^{ex}\equiv (a^{e})^{x}(b^{ex})\equiv (ab)^{ex}\equiv 1{\pmod {p}}$ となる。したがって、位数の法則によって $f\,|\,ex$ となる。$(e,f)=1$ だから、定理 1.6 によって $f\,|\,x$ 同様にして、$(ab)^{xn}\equiv 1$ より、$x$ は $e$ の倍数、したがって $x$ は $m,n$ の公倍数となり、 $x=ef$

したがって $ab$ の位数は $ef>e\ (\because f>1)$ となり、位数がより大きい数を見つけることが出来た。

(ii) $\gcd(e,f)=d>1$ のとき

${\rm {lcm}}(e,f)=l$ とおくと、定理 1.5 より、$dl=ef\iff l={\frac {ef}{d}}=e'f'$ とおいて、$e'\,|\,e,f'\,|\,f,(e',f')=1$ とすることができる。 （※1）

$a^{\frac {e}{e'}},b^{\frac {f}{f'}}$ の位数はそれぞれ、定理 2.2.3 より ${\frac {e}{\gcd({\frac {e}{e'}},e)}}=e',{\frac {f}{\gcd({\frac {f}{f'}},f)}}=f'$ である。（※2）

したがって、$({\frac {e}{e'}},{\frac {f}{f'}})=1$ であることから、(i) より $a^{\frac {e}{e'}}b^{\frac {f}{f'}}$ の位数は $e'f'=l={\rm {lcm}}(e,f)$ となる。

先に述べたように $e$ は $f$ の倍数ではないから $ab$ の位数は $l>e$ となり、やはり $a$ の位数より大きい。

(i), (ii) より、位数が大きい数を生成することが出来た。これを繰り返していけば、アルキメデスの公理から位数が $p-1$ となる数、すなわち原始根が必ずみつかることが証明され、よって原始根の存在も証明された。

注釈

（※1）について :

それぞれを全ての素数による素因数分解をした形、$e=p_{0}^{a_{0}}p_{1}^{a_{1}}\cdots ,f=q_{0}^{b_{0}}q_{1}{b^{1}}\cdots$ を考える。（因数に含まれない素数は指数を 0 にする）

これらの全ての素因数のうち、指数の大きい方をどちらにあるかにしたがって $e',f'$ に分配する。指数が同じならどちらでも構わない。このように分配すれば条件を満たす $e',f'$ を構成できる。

（※2）について :

$e=e'E,f=f'F$ とおくと、${\frac {e}{e'}}=E,{\frac {f}{f'}}=F$ となり、

${\begin{aligned}{\frac {e}{\gcd({\frac {e}{e'}},e)}}&={\frac {e}{\gcd(E,e'E)}}\\&={\frac {e}{E}}\\&=e'\end{aligned}}$

${\begin{aligned}{\frac {f}{\gcd({\frac {f}{f'}},f)}}&={\frac {f}{\gcd(F,f'F)}}\\&={\frac {f}{F}}\\&=f'\end{aligned}}$

$({\frac {e}{e'}},{\frac {f}{f'}})=(e',f')=1$

例 41 の原始根を求めてみる。

まずは、2 の位数を求めると、10 であることが計算すれば分かる（このとき位数の法則より、41-1 = 40 の約数のみを調べれば良い）。

$2^{2}=4,2^{3}=8,2^{4}=16,2^{5}=32,2^{6}\equiv 23,2^{7}\equiv 5,2^{8}\equiv 10,2^{9}\equiv 20,2^{10}\equiv 40$ となり、3 は右辺に出てこない。3 の位数を求めると、8 であることが分かる。

ところで、$2^{\frac {20}{5}}=2^{4}$ の位数は 5 である。$(2^{4},3)=1$ なので上記の証明の (i) の場合に対応する。したがって、$2^{4}\cdot 3=48\equiv 7$ の位数は $5\cdot 8=40$ である。すなわち原始根が見つかったのである。

41 までの素数を法とする原始根は次のとおりである。

素数 $p$ を法とする原始根

p	原始根
3	2
5	2, 3
7	3, 5
11	2, 6, 7, 8
13	2, 6, 7, 11
17	3, 5, 6, 7, 10, 11, 12, 14
19	2, 3, 10, 13, 14, 15
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
31	3, 11, 12, 13, 17, 21, 22, 24
37	2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35
41	6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35

問 43 を法とする原始根を求めよ。

41 のように、最小原始根が素数ではない場合もある。

このように、与えられた法に対して原始根が存在することは初等的に示される。しかし、逆に与えられた数を原始根に持つ法が存在するか否かは明らかではない。累乗数が原始根たりえないことは明らかだが、それ以外の数については明らかではない。たとえば、累乗数ではない、どのような数についても、それを原始根に持つ法が無数に存在するか否かは未だに解決されていない。

定理 2.3.1

素数 $p$ を法としての原始根の1つを $r$ とおく。$\{1,r,r^{2},\cdots ,r^{p-2}\}$ は剰余系である。また、どれも $p$ と互いに素である（既約剰余系である）。特に $a$ が $p$ と互いに素な数であるとき $a\equiv r^{l}{\pmod {p}}$ となる整数 $l(0\leq l\leq p-2)$ が1つ定まる。

原始根の存在証明の中で、すでにどれも互いに不合同であることは証明されている。また法は素数であることから、これらはどれも $p$ と互いに素で、剰余系をなす。

フェルマーの小定理と併せて、上記の $l$ に対し $a\equiv r^{k}{\pmod {p}}\iff k\equiv l{\pmod {p-1}}$ となることがわかる。

定理 2.3.2

$a$ が $p$ と互いに素な数とする。素数 $p$ を法としての原始根の1つを $r$ とし $k$ を $a\equiv r^{k}{\pmod {p}}$ となる整数とおくと $a{\pmod {p}}$ の位数は $(p-1)/\gcd(p-1,k)$ に等しい。

実際このとき定理 1.6' より $a^{e}\equiv 1{\pmod {p}}\iff r^{ke}\equiv 1{\pmod {p}}\iff (p-1)\,|\,ke\iff (p-1)/\gcd(p-1,k)\,|\,e$ である。

原始根・指数

定理 2.3.1 で見たように法の素数を $p$ とおき、$r$ を原始根とすると、任意の $n$ について

$r^{a}\equiv n{\pmod {p}}$ となる $0\leqq a<p-1$ がただ一つ存在する。この $a$ を 「$r$ を底とする $n$ の指数 (index)」という。またこれを、次のように表記する。

$\mathrm {Ind} _{r}n=a$ あるいは$\mathrm {log} _{r}n=a.$

定理 2.3.1 で見たように

$a\equiv b{\pmod {p}}\iff \mathrm {Ind} _{r}a=\mathrm {Ind} _{r}b$

であることがわかる。

$p,r$ をそれぞれ素数とその原始根とすると、

$r^{s}\equiv n{\pmod {p}}\iff s\equiv \mathrm {Ind} _{r}\,n{\pmod {p-1}}$

であることがわかる。

次に見るように、指数は対数関数と類似した性質を持っている。それで、指数を$r$ を底とする $n$ の離散対数 (discrete logarithm)と呼ぶこともある（古くから指数と呼ばれていたが、近年、暗号系への応用に伴って、離散対数問題として知られるようになった）。

定理 2.3.3

素数 $p$ に対し $a,b$ を $p$ と互いに素な数、 $r,r'$ を $p$ を法とする原始根とすると、

${\begin{cases}\mathrm {Ind} _{r}ab\equiv \mathrm {Ind} _{r}a+\mathrm {Ind} _{r}b,\\\mathrm {Ind} _{r}a^{n}\equiv n\mathrm {Ind} _{r}a,\\\mathrm {Ind} _{r'}a=\mathrm {Ind} _{r'}r\mathrm {Ind} _{r}a\end{cases}}{\pmod {p-1}}.$

証明
$\mathrm {Ind} _{r}a=\alpha ,\mathrm {Ind} _{r}b=\beta$ とおくと、定義より $r^{\alpha }\equiv a,r^{\beta }\equiv b{\pmod {p}}$ であるから $ab\equiv r^{\alpha +\beta }{\pmod {p}}$ がすぐに分かる。よって

$\mathrm {Ind} _{r}\,ab\equiv \alpha +\beta \equiv \mathrm {Ind} _{r}\,a+\mathrm {Ind} _{r}\,b{\pmod {p-1}}$

ここから $\mathrm {Ind} _{r}a^{n}\equiv n\mathrm {Ind} _{r}a$ は $n$ に関する数学的帰納法で容易に証明される。

また $\mathrm {Ind} _{r}a=\alpha ,\mathrm {Ind} _{r'}r=\rho$ とおくと $r^{\alpha }\equiv a,\ r'^{\rho }\equiv r{\pmod {p}}$ より $r'^{\rho \alpha }=(r'^{\rho })^{\alpha }\equiv r^{\alpha }\equiv a{\pmod {p}}$ なので $\mathrm {Ind} _{r'}a\equiv \rho \alpha \equiv \mathrm {Ind} _{r'}r\mathrm {Ind} _{r}a{\pmod {p-1}}$ である。

原始根の応用例

$p\neq 2,r$ をそれぞれ素数とその原始根とする。

(1) $r^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ つまり $\mathrm {Ind} _{r}(-1)={\frac {p-1}{2}}$ である。

証明
$(r^{\frac {p-1}{2}})^{2}\equiv r^{p-1}\equiv 1{\pmod {p}}$ であるが $x^{2}\equiv 1{\pmod {p}}$ の解は $x\equiv \pm 1{\pmod {p}}$ だから $r^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}$ がわかる。しかし $r$ は原始根であるから $r^{\frac {p-1}{2}}\not \equiv 1{\pmod {p}}$ なので $r^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ でなければならない。

(2) $a+b=p$ のとき $\mathrm {Ind} _{r}a-\mathrm {Ind} _{r}b\equiv {\frac {p-1}{2}}{\pmod {p-1}}$

証明
実際 $a\equiv -b{\pmod {p}}$ なので

$\mathrm {Ind} _{r}a\equiv \mathrm {Ind} _{r}(-b)\equiv \mathrm {Ind} _{r}(-1)+\mathrm {Ind} _{r}b={\frac {p-1}{2}}+\mathrm {Ind} _{r}b{\pmod {p-1}}$

である。

(3) $k$ が $p-1$ で割り切れないとき、

$1^{k}+2^{k}+3^{k}+\cdots +(p-1)^{k}\equiv 0{\pmod {p}}.$

証明
原始根のべき乗は既約剰余系を成すので、この和は

$\sum _{a=1}^{p-1}a^{k}\equiv \sum _{l=0}^{p-2}r^{lk}{\pmod {p}}$

となる。これを $r^{k}-1$ 倍すると

$(r^{k}-1)\sum _{a=1}^{p-1}a^{k}\equiv r^{(p-1)k}-1\equiv 0$

となるが、$r$ は $p$ を法とする原始根だから $r^{k}\not \equiv 1$ である。したがって、

$\sum _{a=1}^{p-1}a^{k}\equiv 0$

となる。

また、原始根をウィルソンの定理の別証明に用いることもできる。

$(p-1)!\equiv r^{0}r^{1}r^{2}\cdots r^{p-2}\equiv r^{0+1+2+\cdots +(p-2)}\equiv (r^{\frac {p-1}{2}})^{p-2},$

ここで (1) より $r^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$ なので $(p-1)!\equiv (-1)^{p-2}$ となるが、$p$ は奇素数なので、これは -1 に合同である。 また $(2-1)!=1!=1\equiv -1{\pmod {2}}$ であるから、ウィルソンの定理が証明された。

原始根とべき剰余

$x^{n}\equiv a{\pmod {p}}$ が解を持つか、持たないかにしたがって $a$ を $p$ の $n$ 次剰余（べき剰余）、非剰余という。 べき剰余について、次の基本的な定理が成り立つ。

定理 2.3.4

$p$ を素数、$a$ を $p$ で割り切れない数とする。$n\neq 0$ を整数とし $e=\gcd(n,p-1),f=(p-1)/e$ とおく。 このとき次の3つはいずれも同値である。

• $x^{n}\equiv a{\pmod {p}}$ が解を持つ。
• $e|\mathrm {Ind} _{r}a.$
• $a^{f}\equiv 1{\pmod {p}}.$

またこのとき $x^{n}\equiv a{\pmod {p}}$ の解の1つを $x_{0}$ とすると、この合同方程式の解は

$x_{0}r^{fl},l=0,1,\ldots e-1$

の $e$個である。

証明
$r$ を原始根とし $k=\mathrm {Ind} _{r}a$ とおく。 $t=n/e$ とおくと $\gcd(t,f)=1$ より $tu\equiv 1{\pmod {f}}$ となる整数 $u$ が存在する。 第一に $e|k$ ならば $x=r^{ku/e}$ は解である。実際

$x^{n}=(r^{ku/e})^{n}=r^{kun/e}=r^{ktu}$

となるが $(p-1)|ef|kf|k(tu-1)$ より $ktu\equiv k{\pmod {p-1}}$ だから

$x^{n}=r^{ktu}\equiv r^{k}\equiv a{\pmod {p}}.$

第二に $x^{n}\equiv a{\pmod {p}}$ ならば $nf=n(p-1)/\gcd(n,p-1)=(p-1)t$ より $a^{f}\equiv x^{nf}\equiv 1{\pmod {p}}$ である。

第三に $a^{f}\equiv 1{\pmod {p}}$ とする。$r$ を原始根とし $k=\mathrm {Ind} _{r}a$ とおくと $r^{kf}\equiv 1{\pmod {p}}$ つまり $(p-1)|kf$ であるから $e=(p-1)/f|k$ である。

さて $x^{n}\equiv a{\pmod {p}}$ の解が存在するとして $x_{0}=r^{m}$ を解の1つとする。 このとき 定理 1.6' より

$r^{sn}\equiv 1{\pmod {n}}\iff (p-1)|sn\iff f|s$

であるから

$(x_{0}r^{s})^{n}\equiv a\iff ar^{sn}\equiv a\iff f|s$

となる。 $ef=p-1$ より解は $x_{0}r^{fl},l=0,1,\ldots e-1$ の $e$ 個である。

このことから、$e=\gcd(n,p-1)$ とおくと $x^{n}\equiv a{\pmod {p}}$ が解を持つことと $x^{e}\equiv a{\pmod {p}}$ が解を持つことは同値であることがすぐにわかる。 よって、べき剰余を考える上では、 $n$ が $p-1$ の約数のときが本質的であると言える。

$n>1$ が $p-1$ の約数のとき $n$ 次剰余は原始根ではない。なぜなら $a^{(p-1)/n}\equiv 1{\pmod {p}}$ より $a$ の位数は $p-1$ より小さくなるからである。

べき剰余については、後に初等整数論/べき剰余で詳しく考察する。