SNNN数の巡回定理
説明 (informal)
以下$ \mathrm{o}_G(x)を$ xの群$ Gにおける位数を表すものとして用いる. $ xから位数計算の対象となる群が一意に定まる場合, $ Gは省略される.
出典
$ \forall a, b, s\in\mathbb{Z}. $ \forall m, n\in\mathbb{N}. $ p\in\mathbb{P}. $ \gcd(p, a) = 1\land a\ne 1. このとき$ u_p\in\mathbb{N}\setminus\lbrace\,0\,\rbraceが存在し, $ u_pは$ pを法とした$ S_{a, b, s}の基本周期である. 特に
$ u_p = \begin{cases}1 & (p\mid D)\cr p&(p\nmid D \land p\mid (a-1))\cr \mathrm{o}_{\mathbb{F}_p^\times}(a) & (\text{otherwise})\end{cases}.
$ \forall a, b, s\in\mathbb{Z}. $ \forall m, n, k\in\mathbb{N}. $ p\in\mathbb{P}. $ \gcd(p, a) = 1\land 1\leq k\land a\ne 1. このとき$ u_{p^k}\in\mathbb{N}\setminus\lbrace\,0\,\rbraceが存在し, $ u_{p^k}は$ p^kを法とした$ S_{a, b, s}の基本周期である. 特に
$ u_{p^k} = \begin{cases}1 & (k\leq v_p(D) - v_p(a-1) + v_2(p))\cr \mathrm{o}_{(\mathbb{Z}/p^{k - v_p(D)+v_p(a-1)}\mathbb{Z})^\times}(a) & (\text{otherwise})\end{cases}.
$ \forall a, b, s\in\mathbb{Z}. $ \forall m, n, k\in\mathbb{N}. $ p\in\mathbb{P}. $ \gcd(p, a) = 1\land 1\leq k\land a\ne 1. このとき$ u_{p^k}\in\mathbb{N}\setminus\lbrace\,0\,\rbraceが存在し, $ u_{p^k}は$ p^kを法とした$ S_{a, b, s}の基本周期である. 特に$ t := 2^{v_2(p)}について
$ u_{p^k} = \begin{cases}1 & (k\leq v_p(D) - v_p(a-1) + v_2(p))\cr p^{\max(0, k-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a) & (\text{otherwise})\end{cases}
ただし
$ \tilde{k_p} = \begin{cases}v_p(D)-v_p(a-1)+W_p(a) & (p\ne 2)\cr v_2(D) & (p = 2\land a\equiv 1\pmod 4)\cr v_2(D)+v_2(a+1) & (p = 2\land a\equiv 3\pmod 4)\end{cases}
Cor. 3はThm. 1を利用していない. これはThm. 2がThm. 1の整合的な拡張になっているためである. 整合性証明はProp. Aによる.
Proof for Thm. 1
$ p\mid Dのとき
一般性を失わず$ m\leq nを仮定してよい.
次が成立する:
$ \begin{aligned}S_{a, b, s}(1) - S_{a, b, s}(0) &= ((aD-b) - (D - b)) / (a-1)\cr &= aD(a - 1) / (a-1)\cr &= aD\end{aligned}
$ p\mid Dより$ S_{a, b, s}(1) \equiv S_{a, b, s}(0)\pmod p.
1より小さな周期は存在せず, これゆえ$ u_z = 1が基本周期である.
$ p\nmid Dかつ$ p\mid (a-1)のとき
$ \forall n\in\mathbb{N}. に対して次が成立.
$ \begin{aligned}S_{a, b, s}(n)&\equiv a^ns+b(1+a+a^2+\cdots+a^{n-1})\cr&\equiv 1^ns+b(1+1+1^2+\cdots+1^{n-1})\cr &\equiv s+bn\pmod p\end{aligned}.
すると $ S_{a, b, s}(n) - S_{a, b, s}(0) \equiv 0\pmod p \iff bn \equiv 0\pmod p. である.
$ p\nmid Dかつ$ D \equiv (a-1)s + b \equiv b\pmod pより$ b\not\equiv 0\pmod p. したがって$ p\mid n.
$ pを約数にもつ最も小さな自然数は$ pであるから, SNNN数の周期 Lem. Bより基本周期$ u_zは$ pである. その他のとき
この場合$ p\nmid Dかつ$ p\nmid (a-1)を仮定してよい.
まず次が成立する:
$ \begin{aligned}S_{a, b, s}(n) - S_{a, b, s}(0)&\equiv (a^nD-b)/(a-1) - s\cr&\equiv (a^n(a-1)s+a^nb - b - s(a-1))/(a-1)\cr&\equiv ((a-1)s(a^n-1)+(a^n-1)b)/(a-1)\cr&\equiv ((a-1)s+b)(a^n-1)/(a-1)\cr&\equiv D(a^n-1)/(a-1)\pmod p\end{aligned}
次に$ D(a^n-1)/(a-1) \equiv 0\pmod p\iff D(a^n-1)\equiv 0\pmod p\iff a^n\equiv 1\pmod pである.
$ a^n\equiv 1\pmod pをみたす最小の$ nは$ \mathrm{o}(a)に他ならない. したがって基本周期$ u_zは$ \mathrm{o}(a)である. $ \Box
Proof for Thm. 2
SNNN数の周期 Lem. Aより$ \exists u\in\mathbb{N}. $ S(u)\equiv S(0)\pmod {p^k}. を示せばよい. このとき次が成立. $ \begin{aligned}S(u)\equiv S(0)\pmod {p^k} &\iff (a^uD-b)/(a-1)\equiv b\pmod {p^k}\cr&\iff D(a^u - 1)/(a-1)\equiv 0\pmod {p^k}\cr &\iff k\leq v_p(D(a^u-1)/(a-1))\end{aligned}
$ v_p(D(a^u - 1) / (a-1)) = v_p(D)+v_p(a^u - 1) - v_p(a-1)より$ k-v_p(D)+v_p(a-1)\leq v_p(a^u-1)\iff a^u\equiv 1\pmod {p^{\max(0, k-v_p(D)+v_p(a-1))}}.
$ k\leq v_p(D)-v_p(a-1)のとき$ p^0 = 1で成立するため, $ u = 1.
$ p = 2の場合$ (\mathbb{Z}/2\mathbb{Z})^\times\simeq \lbrace\,1\,\rbraceであることから$ k-v_p(D)+v_p(a-1) = 1の場合も$ u = 1
$ p = 2\iff v_2(p) = 1かつ$ p\ne 2\iff v_2(p) = 0であるため, $ u = 1\iff k\leq v_p(D)-v_p(a-1) + v_2(p)である.
$ k\gt v_p(D) - v_p(a-1)のとき, $ a^u\equiv 1\pmod {p^{k - v_p(D)+v_p(a-1)}}を満たす最小の非零自然数が$ uである. これは$ (\mathbb{Z}/p^{k - v_p(D)+v_p(a-1)}\mathbb{Z})^\timesにおける$ aの位数に他ならない. $ \Box
Proof for Cor. 3.
$ k\leq v_p(D) - v_p(a-1) + v_2(p)のときはThm. 2よりよい.
その他の場合, Thm. 2より$ u_{p^k} = \mathrm{o}_{(\mathbb{Z}/p^{k - v_p(D)+v_p(a-1)}\mathbb{Z})^\times}(a). ここで素数冪乗法群の位数計算定理 Thm. 1を用いて計算した結果がステートメントのものと一致することを示す. $ p\ne 2のとき
$ t = 1より$ u_{p^k} = p^{\max(0, k-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a)を示せばよい
$ \begin{aligned}u_{p^k} &= p^{\max(0, k - v_p(D)+v_p(a-1) - W_p(a))}\cdot\mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a)\cr &= p^{\max(0, k - (v_p(D) - v_p(a-1) + W_p(a)))}\cdot\mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a)\cr &= p^{\max(0, k - \tilde{k_p})}\cdot\mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a)\end{aligned}
$ p = 2のとき
$ t = 2より$ u_{p^k} = p^{\max(0, k-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a)を示せばよい
$ a\equiv 1\pmod 4のとき
$ \begin{aligned}u_{2^k} &= 2^{\max(0, k+v_2(a-1)-v_2(D) - v_2(a-1))}\cr& = 2^{\max(0, k-v_2(D))}\cr&= 2^{\max(0, k-\tilde{k_p})}\end{aligned}
$ a\equiv 1\pmod 4\implies \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a) = 1であるから$ u_{2^k} = 2^{\max(0, k-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a).
$ a\equiv 3\pmod 4のとき
$ u_{2^k} = 2^{\max(1, k + v_2(a-1) - v_2(D) - v_2(a + 1))}.
$ a\equiv 3\pmod 4\iff a-1\equiv 2\pmod 4であるから$ v_p(a-1) = 1.
また$ a^2 \equiv 9\equiv 1\pmod 4より$ \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a) = 2.
以上より次が成立
$ \begin{aligned}u_{2^k} &= 2^{\max(1, 1 + k - v_2(D) - v_2(a + 1))}\cr &= 2^{\max(0, k - v_2(D) - v_2(a + 1))}\cdot 2\cr&= 2^{\max(0, k - (v_2(D) + v_2(a + 1)))}\mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a)\cr &= 2^{\max(0, k - \tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a)\end{aligned}
いずれの場合も成立. $ \Box
Prop. A (informal)
Thm. 2において, $ k = 1とおくとThm. 1が従う. 換言すれば, Thm. 2はThm. 1の別証明であり, なおかつ整合的な拡張である.
Prop. A (formal)
$ \forall a, b, s\in\mathbb{Z}. $ \forall m, n\in\mathbb{N}. $ p\in\mathbb{P}. $ \gcd(p, a) = 1\land a\ne 1. Cor. 3より$ \exists u_{p^1}\in\mathbb{N}. $ u_{p^1}は$ p^1 = pを法とした$ S_{a, b, s}の基本周期かつ$ t := 2^{v_2(p)}について
$ u_{p^1} = \begin{cases}1 & (1\leq v_p(D) - v_p(a-1) + v_2(p))\cr p^{\max(0, 1-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a) & (\text{otherwise})\end{cases}. ただし $ \tilde{k_p} := \begin{cases}v_p(D)-v_p(a-1)+W_p(a) & (p\ne 2)\cr v_2(D) & (p = 2\land a\equiv 1\pmod 4)\cr v_2(D)+v_2(a+1) & (p = 2\land a\equiv 3\pmod 4)\end{cases} .
このとき$ u_{p^1} = \begin{cases}1 & (p\mid D)\cr p&(p\nmid D \land p\mid (a-1))\cr \mathrm{o}_{\mathbb{F}_p^\times}(a) & (\text{otherwise})\end{cases}.
Cor. 3はThm. 2から直接従うため, 整合性を確認するために利用して問題ない.
Proof.
$ p\mid Dのとき: $ v_p(D) \geq 1.
$ p = 2かつ$ a\equiv 3\pmod 4のとき
$ a - 1 = 2\pmod 4より$ v_2(a - 1) = 1.
$ v_2(D) - v_2(a-1)+v_2(2) = v_2(D) - 1 + 1 = v_2(D)\geq 1より$ u_{p^1} = 1.
$ 1\leq v_p(D) - v_p(a-1) + v_2(p)のとき
定義より$ u_{p^1} = 1.
$ 1\gt v_p(D) - v_p(a-1) + v_2(p)のとき
$ 1\leq v_p(D)\lt 1 + v_p(a-1) - v_2(p)である.
$ v_2(p) = 0のとき
$ 1\leq v_p(D)\lt 1 + v_p(a-1)より$ 1\leq v_p(a-1).
$ v_2(p) = 1のとき
$ 1\leq v_p(D)\lt v_p(a-1)より$ 2\leq v_p(a-1).
いずれの場合も$ p\mid (a-1)である.
$ p\ne 2のとき
Wieferich階数 Prop. 2より$ v_p(a-1) = W_p(a). よって$ \tilde{k_p} = v_p(D)-v_p(a-1)+W_p(a) = v_p(D)\geq 1. $ p\mid (a-1)\iff a\equiv 1\pmod pより$ \mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a) = 1.
$ p = 2かつ$ a\equiv 1\pmod 4のとき
$ \tilde{k_p} = v_p(D)\geq 1.
$ \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(1) = 1.
いかなる場合も$ \tilde{k_p}\geq 1であることから$ 1 - \tilde{k_p}\leq 0.
そして$ \mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a) = 1なので$ u_{p^1} = 1.
$ p\nmid Dのとき: $ v_p(D) = 0.
$ p\mid(a-1)のとき: $ v_p(a-1)\geq 1.
$ v_p(D) - v_p(a-1)+v_2(p) = v_2(p) - v_p(a-1) \leq 0より$ u_{p^1} = p^{\max(0, 1-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a).
$ pごとに場合分けして示す
$ p\ne 2のとき
$ p\mid (a-1)\iff a\equiv 1\pmod pより$ \mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a) = 1.
Wieferich階数 Prop. 2より$ \tilde{k_p} = v_p(D) - v_p(a-1) + W_p(a) = 0. よって$ 1 - \tilde{k_p} = 1なので$ u_{p^1} = p\cdot \mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a) = p.
$ p = 2かつ$ a\equiv 1\pmod 4のとき
$ \tilde{k_p} = v_2(D) = 0.
$ \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(1) = 1.
よって$ 1 - \tilde{k_p} = 1ゆえ$ u_{p^1} = p\cdot \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a) = p.
$ p = 2かつ$ a\equiv 3\pmod 4のとき
$ \tilde{k_p} = v_2(D) + v_2(a+1) = v_2(a+1)\geq 2.
$ \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(3) = 2.
$ 1 - \tilde{k_p} \leq -1より$ u_{p^1} = \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a) = 2 = p.
$ p\nmid (a-1)のとき: $ v_p(a-1) = 0.
$ p\ne 2のとき
$ v_2(p) = 0.
$ v_p(D) - v_p(a-1) + v_2(p) = 0 - 0 + 0 = 0\lt 1より$ u_{p^1} = p^{\max(0, 1-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a).
$ \tilde{k_p} = v_p(D) - v_p(a-1) + W_p(a) = W_p(a)\geq 1.
よって$ k - \tilde{k_p}\leq 0であるから$ u_{p^1} = \mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a).
$ p = 2のとき
$ v_2(p) = 1.
$ v_p(D) - v_p(a-1) + v_2(p) = 0 - 0 + 1 = 1\geq 1より$ u_{p^1} = 1. $ \Box