素因数 $2$ の取り扱いについて

更新日：2022/9/30

※ 本記事は位数定理を取り扱う都合上，群論の基礎知識を前提として議論を進める．難解であれば読み飛ばしても差し支えないが，その場合はページ末尾の結論のみ確認されたい．

位数定理や素数冪の巡回定理は，$p$ が奇素数であるという条件のもとで成立していた．それでは，$p=2$ の場合はどうなるだろうか．実はこのとき，位数定理の証明に用いた群同型 $$ (\Z/p^k\Z)^\times \simeq \Z/p^{k-1}\Z \times \Z/(p-1)\Z $$ が成立しないのである．したがって，位数定理に関連する議論を修正する必要がある．

$p=2$ の場合の位数定理・素数冪の巡回定理

$\ord_{2^k}(a)$ について，$k=1$ の場合は明らかに $\ord_2(a)=1$ であるから，以下では $k\ge 2$ の場合を考える．$(\Z/2^k\Z)^\times$ において，$x\in(\Z/2^k\Z)^\times$ が生成する部分群を $\lang x\rang$ と表記する．$k\ge 2$ であるとき，$(\Z/2^k\Z)^\times$ の群構造は $$ \begin{align*} (\Z/2^k\Z)^\times &\simeq \lang -1 \rang \times \lang 5 \rang \\ &\simeq \Z/2\Z \times \Z/2^{k-2}\Z \\ \end{align*} $$ となることが知られている（証明はこちら）．よって，十分大きな整数 $K$ に対し，$2$ と互いに素な整数 $a$ が $a\equiv (-1)^{a''} \cdot 5^{a'} \mod{2^K}$ と表示されるとき，$1\le k\le K$ の範囲で $$ \begin{equation} \ord_{2^k}(a) = \lcm( \ord_{\Z/2\Z}(a''), \ord_{\Z/2^{k-2}\Z}(a') ) \end{equation} $$ が成り立つ．この式に $k=2$ を代入すると $$ \begin{align*} \ord_{2^2}(a) &= \lcm( \ord_{\Z/2\Z}(a''), \ord_{\Z/\Z}(a') ) \\ &= \lcm( \ord_{\Z/2\Z}(a''), 1 ) \\ &= \ord_{\Z/2\Z}(a'') \\ \end{align*} $$ を得る．さらに，$\ord_{\Z/2\Z}(a'')\in\{1,2\}$ より $\ord_{2^2}(a)\in\{1,2\}$ であるから $$ \begin{equation} \begin{split} \ord_{\Z/2\Z}(a'') &= \ord_{2^2}(a) \\ &= 2^{\ord_{2^2}(a)-1} \\ \end{split} \end{equation} $$ が成り立つ．一方，$\ord_{\Z/2^{k-2}\Z}(a')$ については，$p$ が奇素数の場合と同様の補題を用いて $$ \begin{align} \ord_{\Z/2^{k-2}\Z}(a') = 2^{\max(0,k-2-\nu_2(a'))} \end{align} $$ と表される．(2),(3)式を(1)式に代入すると $$ \begin{equation} \begin{split} \ord_{2^k}(a) &= \lcm( 2^{\ord_{2^2}(a)-1}, 2^{\max(0,k-2-\nu_2(a'))} ) \\ &= 2^{\max(\ord_{2^2}(a)-1, 0, k-2-\nu_2(a'))} \\ &= 2^{\max(\ord_{2^2}(a)-1, k-2-\nu_2(a'))} \\ \end{split} \end{equation} $$ を得る．この式と $\ord_{2^2}(a)=2^{\ord_{2^2}(a)-1}$ より $$ \begin{equation} \begin{split} \ord_{2^k}(a) = \ord_{2^2}(a) &\iff 2^{\max(\ord_{2^2}(a)-1, k-2-\nu_2(a'))} = 2^{\ord_{2^2}(a)-1} \\ &\iff \ord_{2^2}(a)-1 \ge k-2-\nu_2(a') \\ &\iff k \le 1+\nu_2(a')+\ord_{2^2}(a) \end{split} \end{equation} $$ が成り立つ．一方，位数の定義より $$ \begin{equation} \begin{split} \ord_{2^k}(a) = \ord_{2^2}(a) &\iff a^{\ord_{2^2}(a)}\equiv 1\mod{2^k} \\ &\iff \nu_2(a^{\ord_{2^2}(a)}-1) \ge k \\ \end{split} \end{equation} $$ であるから，(5),(6)式を比較して $$ \begin{align*} 1+\nu_2(a')+\ord_{2^2}(a) &= \nu_2(a^{\ord_{2^2}(a)}-1) \\ \nu_2(a') &= \nu_2(a^{\ord_{2^2}(a)}-1) - \ord_{2^2}(a) - 1 \\ \end{align*} $$ となり，これを(4)式に代入して $$ \begin{align} \ord_{2^k}(a) = 2^{\max( \ord_{2^2}(a)-1, k-1-\nu_2(a^{\ord_{2^2}(a)}-1)+\ord_{2^2}(a) )} \end{align} $$ を得る．ここで，$a$ を $4$ で割った余りに応じて場合分けを行う．

$a\equiv 1\mod{4}$ の場合

(7)式に $\ord_{2^2}(a)=\ord_4(1)=1$ を代入して $$ \ord_{2^k}(a)=2^{\max(1-1,k-1-\nu_2(a^1-1)+1)}=2^{\max(0,k-\nu_2(a-1))} $$ となる．

$a\equiv 3\mod{4}$ の場合

(7)式に $\ord_{2^2}(a)=\ord_4(3)=2$ を代入して $$ \ord_{2^k}(a)=2^{\max(2-1,k-1-\nu_2(a^2-1)+2)}=2^{\max(1,k+1-\nu_2(a^2-1))} $$ となる．さらに $$ \nu_2(a^2-1)=\nu_2(a-1)+\nu_2(a+1)=1+\nu_2(a+1) $$ を代入して $$ \ord_{2^k}(a)=2^{\max(1,k-\nu_2(a+1))} $$ を得る．

以上の結果を定理として以下に記す．

位数定理 $(p=2)$ 正整数 $k$ と奇数 $a$ に対し， $$ \ord_{2^k}(a)=\begin{cases} 1 & \text{if }k=1 \\ 2^{\max(0,k-\nu_2(a-1))} & \text{if }k>1\text{ and }a\equiv 1\mod{4} \\ 2^{\max(1,k-\nu_2(a+1))} & \text{if }k>1\text{ and }a\equiv 3\mod{4}. \end{cases} $$

この結果を用いて，素数冪の巡回定理が導かれる．導出は演習問題とする．

素数冪の巡回定理 $(p=2)$ 一般化SNNN数列 $S_{a,b,s}$ が $2\nmid a,\;a\neq 1$ を満たすならば，$S_{a,b,s}$ は任意の自然数 $k$ に対して $2^k$ を法とする基本周期 $u_{2^k}$ を持ち， $$ u_{2^k}=\begin{cases} 1 & \text{if } k\le \nu_2(D)-\nu_2(a-1)+1 \\ 2^{\max(0,k-\~k_2)} \cdot \ord_4(a) & \text{otherwise } \\ \end{cases} $$ が成り立つ．ただし $$ \~k_2 = \begin{cases} \nu_2(D) & \text{if }a\equiv 1\mod{4} \\ \nu_2(D)+\nu_2(a+1) & \text{if }a\equiv 3\mod{4}. \\ \end{cases} $$

なお，$k\ge\~k_2$ の範囲で $u_{2^{k+1}}=2u_{2^k}$ が成り立つことから，$p$ が奇素数である場合と同様の系が成立する．