文献あり

合同方程式 x^k≡1 (mod p^e)の解

331

はじめに

　この記事では合同方程式
$x^{k} \equiv 1 (\mod p^{e})$
の $gcd (k, p - 1) \leq 2$ における解を求めます。
　具体的には以下の結果が得られます。なお $p$ は素数とし、 $e, e^{'}$ は
・ $p = 2$ のとき $1 \leq e^{'} \leq e - 2$
・ $p \geq 3$ のとき $0 \leq e^{'} \leq e - 1$
なる整数とします。

$k^{'} = {\begin{cases} gcd (k, 2^{e - 2}) & (p = 2) \\ gcd (k, p^{e - 1} (p - 1)) & (p \geq 3) \end{cases}$
とおいたとき、整数 $x$ が合同方程式
$x^{k} \equiv 1 (\mod p^{e})$
を満たすことと
$x^{k^{'}} \equiv 1 (\mod p^{e})$
を満たすことは同値である。

$p = 2$ のとき
$x^{2^{e^{'}}} \equiv 1 (\mod 2^{e})$ の解は $x \equiv \pm (1 + 2^{e - e^{'}} j) (\mod 2^{e}) (0 \leq j < 2^{e^{'}})$ で尽くされる。
$p \geq 3$ のとき
$x^{p^{e^{'}}} \equiv 1 (\mod p^{e})$ の解は $x \equiv 1 + p^{e - e^{'}} j (\mod p^{e}) (0 \leq j < p^{e^{'}})$ で尽くされ、
$x^{2 p^{e^{'}}} \equiv 1 (\mod p^{e})$ の解は $x \equiv \pm (1 + p^{e - e^{'}} j) (\mod p^{e}) (0 \leq j < p^{e^{'}})$ で尽くされる。

　なお原始根の公式でも見つからない限り $gcd (k, p - 1) \geq 3$ の場合に関する一般的な結果は得られないものと思われます。
　そしてこの系として以下の事実が成り立ちます。

　整数 $a (p ∤ a)$ を動かしたときに $a^{k^{″}} (\mod p^{e})$ が取りうる値を考えると以下が成り立つ。

$p = 2$ のとき
$a^{2^{e - e^{'} - 2}} \equiv 1 + 2^{e - e^{'}} j (\mod 2^{e}) (0 \leq j < 2^{e^{'}})$
$p \geq 3$ のとき
$\begin{aligned} a^{p^{e - e^{'} - 1} (p - 1)} & \equiv 1 + p^{e - e^{'}} j (\mod p^{e}) & (0 \leq j < p^{e^{'}}) \\ a^{p^{e - e^{'} - 1} \frac{p - 1}{2}} & \equiv \pm (1 + p^{e - e^{'}} j) (\mod p^{e}) & (0 \leq j < p^{e^{'}}) \end{aligned}$

　この系はなかなか面白いもので、例えば $p = 2, e = 5, e^{'} = 2$ とすると任意の奇数 $x$ に対して
$\begin{aligned} x^{2} & \equiv 1, 1 + 8, 1 + 16, 1 + 24 \\ \equiv 1, 9, 17, 25 (\mod 32) \end{aligned}$
が成り立ち、また例えば $p = 3, e = 3, e^{'} = 1$ とすると $3$ の倍数でない任意の整数 $x$ に対して
$\begin{aligned} x^{3} & \equiv \pm 1, \pm (1 + 9), \pm (1 + 18) \\ \equiv \pm 1, \pm 10, \pm 8 (\mod 27) \end{aligned}$
が成り立つことがわかります。
　これらの剰余関係が一々 $x$ に $1$ から $p^{e} - 1$ までの値を代入して確かめなくても簡単にわかるというのは楽なもので、例えば以下のような応用が思い付きます。

　 $x, y, z$ を $0$ でない正数とし、もしも等式 $x^{3} + y^{3} = z^{3}$ が成立しているならば、 $x, y, z$ のうち少なくとも一つは $3$ の倍数であることを示せ。(1998 信州大)

　上の系において $p = 3, e = 2, e^{'} = 0$ とすると $3$ の倍数でない任意の整数 $a$ に対して
$a^{3} \equiv \pm 1 (\mod 9)$
が成り立つので $3 ∤ x y z$ とすると
$\begin{aligned} x^{3} + y^{3} & \equiv \pm 1 \pm 1 \\ = 0, 2, - 2 \\ ≢ \pm 1 \equiv z^{3} (\mod 9) \end{aligned}$
となって矛盾。よって $3 | x y z$ を得る。

$x^{k} \equiv 1 (\mod p^{e})$ の解の個数

　整数 $x$ が合同方程式 $x^{k} \equiv 1 (\mod p^{e})$ を満たすことと $x^{k^{'}} \equiv 1 (\mod p^{e})$ を満たすことは同値である。

　群の一般論より $x \in (Z / p^{e} Z)^{\times}$ が $x^{k} = 1$ を満たすとき $x$ の位数は $k$ を割り切るということと、 $| (Z / p^{e} Z)^{\times} | = p^{e - 1} (p - 1)$ より任意の $x \in (Z / p^{e} Z)^{\times}$ に対して $x^{p^{e - 1} (p - 1)} = 1$ が成り立つことから
$\begin{aligned} x^{k} = 1 & ⟺ ord x ∣ gcd (k, p^{e - 1} (p - 1)) \\ ⟺ x^{k^{'}} = 1 \end{aligned}$
を得る( $p = 2$ のときは(下の命題からもわかるように)任意の $x \in (Z / 2^{e} Z)^{\times}$ に対して $x^{2^{e - 2}} = 1$ が成り立つことが知られているので $k^{'} = gcd (k, 2^{e - 2})$ とできることがわかる)。

　 $(Z / p^{e} Z)^{\times}$ の構造について

$p = 2$ のとき
ある位数 $2^{e - 2}$ の元 $r \in (Z / 2^{e} Z)^{\times}$ が存在し、任意の $x \in (Z / 2^{e} Z)^{\times}$ は
$x = \pm r^{n} (0 \leq n < 2^{e - 2})$
の形に一意的に表せる。
$p \geq 3$ のとき
ある位数 $p^{e - 1} (p - 1)$ の元 $r \in (Z / p^{e} Z)^{\times}$ が存在し、任意の $x \in (Z / p^{e} Z)^{\times}$ は
$x = r^{n} (0 \leq n < p^{e - 1} (p - 1))$
の形に一意的に表せる。

　 (Z/nZ)*の群構造 - INTEGERS 等を参照されたい。

$p = 2$ のとき
$x^{2^{e^{'}}} \equiv 1 (\mod 2^{e})$ の解の個数は丁度 $2^{e^{'} + 1}$ 個である。
$p \geq 3$ のとき
$x^{p^{e^{'}}} \equiv 1 (\mod p^{e})$ の解の個数は丁度 $p^{e^{'}}$ 個であり、
$x^{2 p^{e^{'}}} \equiv 1 (\mod p^{e})$ の解の個数は丁度 $2 p^{e^{'}}$ 個である。

$p = 2$ のとき
命題4のような $r$ に対し、 $x = \pm r^{n}$ が $x^{2^{e^{'}}} = r^{2^{e^{'}} n} = 1$ を満たすことと $2^{e - 2} ∣ 2^{e^{'}} n$ つまり $2^{e - e^{'} - 2} ∣ n$ を満たすことは同値である。そしてそのような $0 \leq n < 2^{e - 2}$ の取り方は
$n = 2^{e - e^{'} - 2} j (0 \leq j < 2^{e^{'}})$
の $2^{e^{'}}$ 通りあるので符号の取り方もあわせて $x$ の取り方は $2^{e^{'} + 1}$ 通りあることになる。
$p \geq 3$ のとき
上と同様にして $x = r^{n}$ が
・ $x^{p^{e^{'}}} = 1$ を満たすとき $n$ の取り方は $n = p^{e - e^{'} - 1} (p - 1) j (0 \leq j < p^{e^{'}})$ の $p^{e^{'}}$ 通り
・ $x^{2 p^{e^{'}}} = 1$ を満たすとき $n$ の取り方は $n = p^{e - e^{'} - 1} \frac{p - 1}{2} j (0 \leq j < 2 p^{e^{'}})$ の $2 p^{e^{'}}$ 通りあることになる。

$x^{k} \equiv 1 (\mod p^{e})$ の解

$p = 2$ のとき
$x \equiv \pm (1 + 2^{e - e^{'}} j) (\mod 2^{e}) (0 \leq j < 2^{e^{'}})$
は合同方程式 $x^{2^{e^{'}}} \equiv 1 (\mod 2^{e})$ を満たす。
$p \geq 3$ のとき
$x \equiv 1 + p^{e - e^{'}} j (\mod p^{e}) (0 \leq j < p^{e^{'}})$
は合同方程式 $x^{p^{e^{'}}} \equiv 1 (\mod p^{e})$ を満たし
$x \equiv \pm (1 + p^{e - e^{'}} j) (\mod p^{e}) (0 \leq j < p^{e^{'}})$
は合同方程式 $x^{2 p^{e^{'}}} \equiv 1 (\mod p^{e})$ を満たす。

　二項定理より
$(1 + p^{e - e^{'}} j)^{p^{e^{'}}} = 1 + \sum_{n = 1}^{p^{e^{'}}} (\binom{p^{e^{'}}}{n}) p^{(e - e^{'}) n}$
と表せるので
$(\binom{p^{e^{'}}}{n}) p^{(e - e^{'}) n} \equiv 1 (\mod p^{e})$
が成り立つことを示せばよい。
　いまルジャンドルの公式から
${ord}_{p} (n!) = \sum_{i = 1}^{\infty} ⌊ \frac{n}{p^{i}} ⌋ < \sum_{i = 1}^{\infty} \frac{n}{p^{i}} = \frac{n}{p - 1} \leq n$
特に ${ord}_{p} (n!) \leq n - 1$ が成り立つことに注意すると
$\begin{aligned} {ord}_{p} ((\binom{p^{e^{'}}}{n}) p^{(e - e^{'}) n}) & = {ord}_{p} (\frac{p^{e^{'}} (p^{e^{'}} - 1) (p^{e^{'}} - 2) \dots (p^{e^{'}} - n + 1)}{n!} p^{(e - e^{'}) n}) \\ \geq {ord}_{p} (p^{e^{'}}) - {ord}_{p} (n!) + {ord}_{p} (p^{(e - e^{'}) n}) \\ \geq e^{'} - (n - 1) + (e - e^{'}) n \\ = e^{'} + (e - e^{'}) + (e^{e^{'}} - 1) (n - 1) \\ \geq e^{'} + (e - e^{'}) = e \end{aligned}$
を得る。

　 $\pm (1 + p^{e - e^{'}} j) (0 \leq j < p^{e^{'}})$ は法 $p^{e}$ においてそれぞれ異なる剰余を持つ。

　 $0 \leq i < j < p^{e^{'}}$ において
$0 \leq 1 + p^{e - e^{'}} i < 1 + p^{e - e^{'}} j \leq 1 + p^{e - e^{'}} (p^{e^{'}} - 1) < p^{e}$
なので $1 + p^{e - e^{'}} i$ と $1 + p^{e - e^{'}} j$ は異なる剰余を持つ。
　また
$1 + p^{e - e^{'}} i \equiv - (1 + p^{e - e^{'}} j) (\mod p^{e})$
が成り立つとすると、この両辺に $p^{e^{'}}$ を掛けることで
$2 p^{e^{'}} \equiv 0 (\mod p^{e})$
となるので $e^{'} \leq e - 1$ より $p = 2, e^{'} = e - 1$ でなければならないが $p = 2$ のときは $e^{'} \leq e - 2$ としていたので矛盾。
　以上より主張を得る。

　命題5と補題7から補題6で挙げた解の個数と方程式の解の個数が一致することがわかるので定理2を得る。

$a^{p^{e - e^{'} - 1} (p - 1)}, a^{p^{e - e^{'} - 1} \frac{p - 1}{2}}$ の剰余

定理2

　整数 $a (p ∤ a)$ を動かしたときに $a^{k^{″}} (\mod p^{e})$ が取りうる値を考えると以下が成り立つ。

$p = 2$ のとき
$a^{2^{e - e^{'} - 2}} \equiv 1 + 2^{e - e^{'}} j (\mod 2^{e}) (0 \leq j < 2^{e^{'}})$
$p \geq 3$ のとき
$\begin{aligned} a^{p^{e - e^{'} - 1} (p - 1)} & \equiv 1 + p^{e - e^{'}} j (\mod p^{e}) & (0 \leq j < p^{e^{'}}) \\ a^{p^{e - e^{'} - 1} \frac{p - 1}{2}} & \equiv \pm (1 + p^{e - e^{'}} j) (\mod p^{e}) & (0 \leq j < p^{e^{'}}) \end{aligned}$

$p \geq 3$ のとき
$x = a^{p^{e - e^{'} - 1} (p - 1)}, a^{p^{e - e^{'} - 1} \frac{p - 1}{2}}$
は $x^{e^{'}} \equiv 1$ や $x^{2 p^{e^{'}}} \equiv 1$ を満たすのである $j$ を用いて
$x \equiv \pm (1 + p^{e - e^{'}} j) (\mod p^{e})$
と表せ、逆に命題5の証明から任意の $j$ に対しある $j^{'}$ が存在して
$\pm (1 + p^{e - e^{'}} j) \equiv (r^{j^{'}})^{p^{e - e^{'} - 1} (p - 1)}, (r^{j^{'}})^{p^{e - e^{'} - 1} \frac{p - 1}{2}} (\mod p^{e})$
が成り立つことから主張を得る。
$p = 2$ のとき
上と同様にある $j$ が存在して
$a^{2^{e - e^{'} - 2}} \equiv \pm (1 + 2^{e - e^{'}} j) (\mod 2^{e})$
と表せるが任意の奇数 $x$ に対し
$x^{2^{e - e^{'} - 2}} \equiv 1 (\mod 2^{e - e^{'}})$
が成り立つことに注意すると符号は正となる。また任意の $j$ にある $j^{'}$ が存在して
$1 + 2^{e - e^{'}} j \equiv \pm (r^{j^{'}})^{2^{e - e^{'} - 2}} (\mod 2^{e})$
が成り立つが
$(r^{j^{'}})^{2^{e - e^{'} - 2}} \equiv 1 (\mod 2^{e - e^{'}})$
なので符号は正となることから主張を得る。