素数冪乗法群の位数計算定理
$ (\mathbb{Z}/p^k\mathbb{Z})^\timesの構造はHenselの補題に代表されるように$ (\mathbb{Z}/p\mathbb{Z})^\timesと深く関係している. 本記事はこの関係を具体的に提示することを目的とする.
出典
以下$ \mathrm{o}_G(x)を$ xの群$ Gにおける位数を表すものとして用いる. $ xから位数計算の対象となる群が一意に定まる場合, $ Gは省略される.
Thm. 1 (formal).
1. $ \forall p\in\mathbb{P}\setminus\lbrace\,2\,\rbrace. $ \forall k\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ \forall a\in\mathbb{N}. $ \gcd(a, p) = 1.
このとき$ \mathrm{o}_{(\mathbb{Z}/p^k\mathbb{Z})^\times}(a) = p^{\max(0, k - W_p(a))}\cdot\mathrm{o}_{(\mathbb{Z}/p\mathbb{Z})^\times}(a).
2. $ \forall k\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ \forall a\in\mathbb{N}. $ \gcd(a, p) = 1.
$ \mathrm{o}_{(\mathbb{Z}/2^k\mathbb{Z})^\times}(a) = \begin{cases}1 & (k = 1) \cr 2^{\max(0, k - v_2(a-1))} & (k\gt 1\land a \equiv 1\pmod 4)\cr 2^{\max(1, k - v_2(a + 1))} & (k\gt 1\land a \equiv 3\pmod 4)\end{cases}
Proof.
1. $ (\mathbb{Z}/p^k\mathbb{Z})^\times\simeq \mathbb{Z}/\varphi(p^k)\mathbb{Z}\simeq \mathbb{Z}/p^{k-1}(p-1)\mathbb{Z}である.
最初の同型において乗法と加法が入れ替わっていることに留意
ここで$ \gcd(p^{k-1}, p-1) = 1であることから$ \mathbb{Z}/p^{k-1}(p-1)\mathbb{Z}\simeq(\mathbb{Z}/p^{k-1}\mathbb{Z})\times(\mathbb{Z}/(p-1)\mathbb{Z}).
$ G = \mathbb{Z}/m\mathbb{Z} ($ mは自然数)とおく. このとき,
1. $ m = m_1m_2($ m_1, m_2は互いに素)なら$ G\simeq (\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})となる.
2. $ mが素数のべき$ p^nなら, $ Gは直既約である.
$ (\mathbb{Z}/p^k\mathbb{Z})^\timesは巡回群なので$ \exists g\in(\mathbb{Z}/p^k\mathbb{Z})^\times. $ (\mathbb{Z}/p^k\mathbb{Z})^\times = \langle g\rangle.
$ \exists n\in\mathbb{N}. $ g^n = a.
$ r:= \mathrm{o}_{\mathbb{Z}/(p-1)\mathbb{Z}}(n).
Lem. Aより次が成立:
$ \begin{aligned}\mathrm{o}_{(\mathbb{Z}/p^k\mathbb{Z})^\times}(g^n) &= \mathrm{o}_{\mathbb{Z}/p^{k-1}(p-1)\mathbb{Z}}(n)\cr &= \operatorname{lcm}(\mathrm{o}_{\mathbb{Z}/p^{k-1}\mathbb{Z}}(n), r)\cr &= \mathrm{o}_{\mathbb{Z}/p^{k-1}\mathbb{Z}}(n)r\end{aligned}
Lem. Bより$ \mathrm{o}_{\mathbb{Z}/p^{k-1}\mathbb{Z}}(g^n) = p^{\max(0, k - 1 - v_p(n))}.
合わせて$ \mathrm{o}_{(\mathbb{Z}/p^k\mathbb{Z})^\times}(g^n) = p^{\max(0, k - 1 - v_p(n))}r.
いま$ \mathrm{o}_{(\mathbb{Z}/p^k\mathbb{Z})^\times}(g^n) = rという条件について考える. この条件を以降条件Xと呼ぶ.
$ \text{条件X} \iff p^{\max(0, k - 1 - v_p(n))} = 1\iff k - 1 - v_p(n)\leq 0より$ \text{条件X} \iff k\leq 1+v_p(n).
他方, 位数の定義より$ \text{条件X} \iff a^{r} - 1\equiv 0\pmod {p^k}\iff k\leq v_p(a^{r} - 1)).
上に見た2条件を比較すると $ \text{条件X}\iff k\leq v_p(a^{r} - 1))\iff k\leq 1+v_p(n).
$ k = 1+v_p(n), $ k = v_p(a^{r} - 1)のそれぞれの場合$ v_p(a^{r} - 1)\leq 1+v_p(n), $ 1+v_p(n)\leq v_p(a^{r} - 1)より$ 1+v_p(n) = v_p(a^{r} - 1)を得る.
一方 Fermatの小定理より$ r\mid (p-1)である.
$ \ell = (p-1) / rとおくとき, Lem. Cより$ \exists f(x)\in\mathbb{F}_p\lbrack x\rbrack. $ x^{p-1} - 1 = (x^{r} - 1)f(x).
特に$ f(a) = \sum_{i=0}^{b-1} a^{ri} = \sum_{i=0}^{\ell-1}1 = \ell だから$ a^{p-1} - 1 = (a^{r} - 1)\ell.
$ \ell\lt p-1\lt pより$ \ell \not\equiv 0\pmod p.
すなわち$ v_p(a^{r} - 1) = v_p(a^{r} - 1) + v_p(\ell) = v_p((a^{r} - 1)\ell) = v_p(a^{p-1} - 1) = W_p(a).
よって$ 1+v_p(n) = W_p(a).
ゆえに$ \mathrm{o}_{(\mathbb{Z}/p^k\mathbb{Z})^\times}(a) = \mathrm{o}_{(\mathbb{Z}/p^k\mathbb{Z})^\times}(g^n) = p^{\max(0, k - W_p(a))}r.
2.
$ k = 1のとき: Z/2^eZの乗法群 Thm. 1 (3.) より$ (\mathbb{Z}/2\mathbb{Z})^\times\simeq \lbrace\,1\,\rbrace. よって$ \mathrm{o}(1) = 1が唯一の対応関係である. $ k\geq 2のとき
次に示すとおり, この場合$ (\mathbb{Z}/2\mathbb{Z})^\times \simeq (\mathbb{Z}/2\mathbb{Z})\times (\mathbb{Z}/2^{k-2}\mathbb{Z})である.
$ k = 2のとき: Z/2^eZの乗法群 Thm. 1 (2.)より$ (\mathbb{Z}/2^2\mathbb{Z})^\times\simeq \mathbb{Z}/2\mathbb{Z}であるから$ \mathbb{Z}/2\mathbb{Z}\simeq(\mathbb{Z}/2\mathbb{Z})\times\lbrace\,1\,\rbrace\simeq (\mathbb{Z}/2\mathbb{Z})\times(\mathbb{Z}/2^{k-2}\mathbb{Z})より成立. $ k\geq 3のとき: Z/2^eZの乗法群 Thm. 1 (1.)より$ (\mathbb{Z}/2\mathbb{Z})^\times \simeq (\mathbb{Z}/2\mathbb{Z})\times (\mathbb{Z}/2^{k-2}\mathbb{Z}). $ \exists g_1\in \mathbb{Z}/2\mathbb{Z}. $ \mathbb{Z}/2\mathbb{Z} = \langle g_1\rangle .
$ \exists g_2\in\mathbb{Z}/2^{k-2}\mathbb{Z}. $ \mathbb{Z}/2^{k-2}\mathbb{Z} \simeq \langle g_2\rangle.
$ \exists \alpha, \beta\in\mathbb{N}. $ a = \alpha\cdot g_1 + \beta\cdot g_2.
乗法と加法の入れ替わりに注意
$ r := \mathrm{o}_{(\mathbb{Z}/2^k\mathbb{Z})^\times}(a).
$ s:= \mathrm{o}_{(\mathbb{Z}/4\mathbb{Z})^\times}(a).
Lem. Aより$ r = \operatorname{lcm}(\mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha), \mathrm{o}_{\mathbb{Z}/2^{k-2}\mathbb{Z}}(\beta)).
$ k = 2の場合$ s = \operatorname{lcm}(\mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha), \mathrm{o}_{\mathbb{Z}/\mathbb{Z}}(\beta)) = \operatorname{lcm}(\mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha), 1) = \mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha)である.
$ \mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha)は$ kに依存せず定まるから, $ s = \mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha)よりこれを定めてよい.
$ \mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha)\in\lbrace\,1, 2\,\rbraceより$ s\in\lbrace\,1, 2\,\rbrace.
他と合わせるために2の冪で表すと$ \mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha) = 2^{s - 1}.
Lem. Bより$ \mathrm{o}_{\mathbb{Z}/2^{k-2}\mathbb{Z}}(\beta) = 2^{\max(0, k - 2 - v_p(\beta))}.
ここまでの結果を代入すると以下の通りである
$ \begin{aligned}r &= \operatorname{lcm}(\mathrm{o}_{\mathbb{Z}/2\mathbb{Z}}(\alpha), \mathrm{o}_{\mathbb{Z}/2^{k-2}\mathbb{Z}}(\beta))\cr &= \operatorname{lcm}(2^{s - 1}, 2^{\max(0, k - 2 - v_p(\beta))})\cr &= 2^{\max(s - 1, \max(0, k - 2 - v_p(\beta)))}\cr &= 2^{\max(0, s - 1, k - 2 - v_p(\beta))}\cr &= 2^{\max(s - 1, k - 2 - v_p(\beta))}.\end{aligned}
いま$ r = sを条件Yとおく.
次が成り立つ.
$ \begin{aligned}\text{条件Y} &\iff 2^{\max(s - 1, k - 2 - v_p(\beta))} = 2^{s - 1}\cr&\iff \max(s - 1, k - 2 - v_p(\beta)) = s - 1\cr&\iff k - 2 - v_p(\beta)\leq s - 1\cr&\iff k\leq s + 1 + v_p(\beta)\end{aligned}
他方, 位数の定義より$ \text{条件Y} \iff a^{s} - 1\equiv 0\pmod {2^k} \iff k\leq v_p(a^{s} - 1).
よって$ k\leq s + 1 + v_p(\beta)\iff k\leq v_p(a^{s} - 1)より$ s + 1 + v_p(\beta) = v_p(a^{s} - 1)を得る.
$ v_p(\beta) = v_p(a^{s} - 1) - s - 1を代入して以下を得る.
$ \begin{aligned} r &= 2^{\max(s - 1, k - 2 - (v_p(a^{s} - 1) - s - 1))}\cr&= 2^{\max(s - 1, k - 2 - v_p(a^{s} - 1) + s + 1)}\cr&= 2^{\max(s - 1, k - 1 - v_p(a^{s} - 1) + s)}.\end{aligned}
$ sは$ a\bmod 4の値で定まるため, 場合分けを実施して簡約する.
$ a\equiv 1\pmod 4のとき
$ s = 1である.
代入して$ r = 2^{\max(0, k - v_p(a - 1))}.
$ a\equiv 3\pmod 4のとき
$ s = 2である.
代入して$ r = 2^{\max(1, k + 1 - v_p(a^{2} - 1))}.
$ v_p(a^2-1) = v_p((a-1)(a+1)) = v_p(a-1)+v_p(a+1), かつ$ a-1\equiv 2\pmod 4より$ v_p(a-1) = 1だから$ v_p(a^2-1) = 1+v_p(a+1).
これを更に代入して$ r = 2^{\max(1, k - v_p(a + 1))}. $ \Box
計算用コード片
code:pk_order_theorem.sage
def compute_order_pk(a, p, k):
assert p.is_prime()
assert gcd(a, p) == 1
assert k > 0
if p == 2:
if k == 1:
return 1
elif a % 4 == 1:
return 2 ^ max(0, k - valuation(a - 1, 2))
elif a % 4 == 3:
return 2 ^ max(1, k - valuation(a + 1, 2))
else:
return p ^ max(0, k - wieferich_order(a, p)) * Mod(a, p).multiplicative_order()
Lem. A (formal).
$ G, H_1, H_2を有限群で$ G \simeq H_1\times H_2と直積分解されるものとし, $ \varphi\colon G\to H_1\times H_2をその同型とする. このとき$ \forall x\in G. $ (x_1, x_2) := \varphi(x). $ \mathrm{o}(x) = \operatorname{lcm}(\mathrm{o}(x_1), \mathrm{o}(x_2)).
Proof.
$ t_0 := \mathrm{o}(x), $ t_1 := \mathrm{o}(x_1), $ t_2 := \mathrm{o}(x_2), $ u := \operatorname{lcm}(t_1, t_2)とおく.
$ t_0 \geq u: $ 1 = \varphi(x^{t_0}) = (x_1^{t_0}, x_2^{t_0})より$ t_0\mid t_1\land t_0\mid t_2 \iff (t_1t_2)\mid t_0\iff u\mid t_0.
$ t_0\leq u: $ \varphi(x^u) = (x_1^u, x_2^u) = (1, 1)より$ t_0\mid u.
$ u\leq t_0\leq uより$ t_0 = u. $ \Box
Lem. B (formal).
$ \forall p\in\mathbb{P}. $ \forall k\in\mathbb{N}. $ \forall n\in\mathbb{Z}. $ \mathrm{o}_{\mathbb{Z}/p^k\mathbb{Z}}(n) = p^{\max(0, k - v_p(n))}.
Proof.
$ t := \mathrm{o}_{\mathbb{Z}/p^k\mathbb{Z}}(n)とおく.
$ nt \equiv 0\pmod {p^k} \iff k\leq v_p(nt)\iff k\leq v_p(n)+v_p(t)\iff k - v_p(n)\leq v_p(t)である.
よって$ t\equiv 0\pmod {p^{\max(0,\ k-v_p(n))}}. $ \Box
Lem. C (formal).
$ Rを可換環, $ \forall a, b\in\mathbb{N}\setminus\lbrace\,0\,\rbraceとする. $ \exists f(x)\in R\lbrack x\rbrack. $ x^{ab} - 1 = (x^a - 1)f(x). とくに$ f(x) = \sum_{i=0}^{b-1} x^{ai}について成立.
多項式除算による構築はとらず, 本記事では正当性を確認することで証明とする. 多項式除算の一意性よりこの$ f(x)を用いることに問題はない.
Proof.
$ f(x) = \sum_{i=0}^{b-1} x^{ai}について$ x^{a}f(x) = \sum_{i=0}^{b-1} x^{a(i+1)} = \sum_{i=1}^{b} x^{ai}である.
よって
$ \begin{aligned}x^af(x) - f(x) &= \left(\sum_{i=1}^{b} x^{ai}\right) - \left(\sum_{i=0}^{b-1} x^{ai}\right)\cr&= x^{ab} + \left(\sum_{i=1}^{b-1} x^{ai}\right) - \left(\sum_{i=1}^{b-1} x^{ai}\right) - 1\cr&= x^{ab}-1.\end{aligned}
$ \Box