位数定理
更新日：2022/9/30
前回の記事で，一般化SNNN数列 $S_{a,b,s}$ の項が素数 $p$ で何回割り切れるかという問題を，$a$ の素因数に限って考察した．それでは，$a$ と互いに素な素数 $p$ についてはどうなるだろうか．巡回定理において，$S_{a,b,s}$ が $p$ で割り切れる周期は位数 $\ord_p(a)$ を用いて記述された．このことから，$p^k$（$k$ は正整数）で割り切れる周期に関して $\ord_{p^k}(a)$ が重要な役割を果たすことは容易に予想されよう．本記事では，素数の累乗を法とする位数に関する重要な定理である位数定理の証明を行う．
位数
位数の定義は巡回定理の記事で紹介したが，ここで改めて述べておこう．
定義 整数 $m$ と，$m$ と互いに素な整数 $a$ に対して，合同方程式 $a^x\equiv 1\mod{m}$ の最小の正の解 $x$ を，法 $m$ における $a$ の位数といい，$\ord_m(a)$ で表す．
例
法 $13$ における $10$ の位数を求める．$x=1,2,3,\cdots$ に対して $10^x$ を $13$ で割った余りを計算すると $$ \begin{align*} 10^1 &\equiv 10 &\mod{13} \\ 10^2 &\equiv 9 &\mod{13} \\ 10^3 &\equiv 12 &\mod{13} \\ 10^4 &\equiv 3 &\mod{13} \\ 10^5 &\equiv 4 &\mod{13} \\ 10^6 &\equiv 1 &\mod{13} \\ \end{align*} $$ となる．よって $\ord_{13}(10)=6$ である．
ヴィーフェリッヒ階数
この節では，位数定理の記述に必要な概念であるヴィーフェリッヒ階数を導入する．
定義 整数 $a$ を底とする素数 $p$ のヴィーフェリッヒ階数 $W_p(a)$ を $$ W_p(a) \coloneqq \nu_p(a^{p-1}-1) $$ で定める（$\nu_p$ の定義はこちら）．
例
$W_3(10)=2,$ $W_7(10)=1,$ $W_{11}(10)=1,$ $W_{13}(10)=1,$ $W_{17}(10)=1,$ $W_{19}(10)=1$.
$a$ が $p$ と互いに素であれば，フェルマーの小定理 $a^{p-1}\equiv 1\mod{p}$ より $W_p(a)\ge 1$ である．実は，ほとんどの $a,p$ に対して $W_p(a)=1$ であり，$W_p(a)>1$ となるような場合は極めて稀である．例えば，底 $a$ が $10$ であるとき，$W_p(10)>1$ となるような $p$ は $3,$ $487,$ $56598313$ の3つのみが知られている．このような $p$ を，$a$ を底とするヴィーフェリッヒ素数という．
位数定理
位数定理 $p$ を奇素数，$k$ を正整数, $a$ を $p$ と互いに素な整数とする．このとき， $$ \ord_{p^k}(a) = p^{\max(0, k-W_p(a))} \cdot \ord_p(a). $$
例
$\ord_{3}(10)=1, W_3(10)=2$ より $\ord_{3^2}(10) = 3^0 \cdot 1 = 1,$ $\ord_{3^3}(10) = 3^1 \cdot 1 = 3,$ $\ord_{3^4}(10) = 3^2 \cdot 1 = 9,$ $\ord_{3^5}(10) = 3^3 \cdot 1 = 27$.
注意 この定理は $p=2$ では成立しない．$p=2$ の取り扱いについてはこちらの記事を参照されたい．
以下，この定理の証明を行う．本サイトでは基本的に高校数学以外の前提知識を仮定しない方針をとっているが，この証明では例外的に群論の基礎知識を前提として議論を進める．難解であれば読み飛ばしても差し支えない．
まず，次の記法を約束する．
- $\Z/m\Z$ や $(\Z/m\Z)^\times$ の元について，$n\in\Z$ の合同類は本来 $[n]$ や $\bar{n}$ などと表記すべきであるが，これを省略して単に $n$ と表記する．
- 一般の群 $G$ における $x\in G$ の位数を $\ord_G(x)$ と表記する．すなわち $\ord_m(n)=\ord_{(\Z/m\Z)^\times}(n)$.
さて，議論の出発点として次の群同型を考える（証明はこちらを参照）． $$ \begin{align*} (\Z/p^k\Z)^\times &\simeq \Z/p^{k-1}(p-1)\Z \\ &\simeq \Z/p^{k-1}\Z \times \Z/(p-1)\Z \end{align*} $$ 法 $p^k$ の原始根を $g$ とおくと，1行目の同型は $g$ の指数関数であり，2行目の同型は自然な写像である．$p^{k-1}$ と $p-1$ は互いに素であるから，$a$ が $a\equiv g^{a'} \mod{p^k}$ と表示されるとき $$ \begin{align} \ord_{p^k}(a) = \ord_{\Z/p^{k-1}\Z}(a') \cdot \ord_{\Z/(p-1)\Z}(a') \end{align} $$ が成り立つ．
この式を用いて，$k$ が変化したときの $\ord_{p^k}(a)$ の変化を考えよう．いま，十分大きな正整数 $K$ をとり，法 $p^K$ の原始根 $g$ を用いて $a\equiv g^{a'}\mod{p^K}$ と表示する．ここで $k$ が $1\le k\le K$ の範囲を動くとき，$g$ は法 $p^k$ の原始根であり，$a$ の表示 $a\equiv g^{a'}\mod{p^k}$ が成立する（$g$ および $a'$ が $k$ に依存しないことに注意せよ）．よって，(1)式において $k=1$ とすれば $$ \begin{align*} \ord_{p^1}(a) &= \ord_{\Z/\Z}(a') \cdot \ord_{\Z/(p-1)\Z}(a') \\ \ord_{p}(a) &= 1 \cdot \ord_{\Z/(p-1)\Z}(a') \\ \end{align*} $$ を得る．これを再び(1)式に代入すると $$ \begin{align} \ord_{p^k}(a) = \ord_{\Z/p^{k-1}\Z}(a') \cdot \ord_p(a) \end{align} $$ となる．
ここで次の補題を用いる．
補題 $p$ を素数, $k$ を自然数，$n$ を整数とする．このとき， $$ \ord_{\Z/p^k\Z}(n) = p^{\max(0, k-\nu_p(n))}. $$
証明
$\ord_{\Z/p^k\Z}(n)$ は，$nx\equiv0 \mod{p^k}$ を満たす最小の正整数 $x$ である．ここで $$ \begin{align*} & nx\equiv 0 \mod{p^k} \\ \iff& \nu_p(nx) \ge k \\ \iff& \nu_p(n) + \nu_p(x) \ge k \\ \iff& \nu_p(x) \ge k - \nu_p(n) \\ \iff& x \equiv 0 \mod{p^{\max(0,k-\nu_p(n))}} \\ \end{align*} $$ であるから補題が成立する．$\blacksquare$
この補題を(2)式に適用すると $$ \begin{align} \ord_{p^k}(a) = p^{\max(0,k-1-\nu_p(a'))} \cdot \ord_p(a) \end{align} $$ となる．この式より $$ \begin{align*} \ord_{p^k}(a)=\ord_p(a) &\iff p^{\max(0,k-1-\nu_p(a'))}=1 \\ &\iff k-1-\nu_p(a')\le 0 \\ &\iff k \le 1+\nu_p(a') \end{align*} $$ が導かれる．一方，位数の定義より $$ \begin{align*} \ord_{p^k}(a)=\ord_p(a) &\iff a^{\ord_p(a)}\equiv 1 \mod{p^k} \\ &\iff \nu_p(a^{\ord_p(a)}-1) \ge k \end{align*} $$ であるから，2つの条件を比較して $$ \begin{align} 1+\nu_p(a') = \nu_p(a^{\ord_p(a)}-1) \end{align} $$ を得る．ここで，$\ord_p(a)$ は $p-1$ の約数であるから $$ a^{p-1}-1 = (a^{\ord_p(a)}-1) \left(a^0 + a^{\ord_p(a)} + a^{2\cdot\ord_p(a)} + \cdots + a^{\left( \frac{p-1}{\ord_p(a)}-1 \right)\cdot\ord_p(a)} \right) $$ が成り立つ．右辺の和を $p$ で割った余りを考えると $$ \begin{align*} & \quad\; a^0 + a^{\ord_p(a)} + a^{2\cdot\ord_p(a)} + \cdots + a^{\left( \frac{p-1}{\ord_p(a)}-1 \right)\cdot\ord_p(a)} \\ &\equiv 1+1+1+\cdots+1 \\ &\equiv \frac{p-1}{\ord_p(a)} \nequiv 0 \qquad\quad\mod{p} \end{align*} $$ であるから， $$ \nu_p(a^{\ord_p(a)}-1) = \nu_p(a^{p-1}-1) = W_p(a) $$ を得る．これと(4)式より $1+\nu_p(a')=W_p(a)$ であるから，これを(3)式に代入して $$ \ord_{p^k}(a) = p^{\max(0, k-W_p(a))} \cdot \ord_p(a) $$ となる．以上で位数定理が示された．
