ウィルソンの定理の拡張 後編 Ex 10.1(b)

今回もシルヴァーマン『はじめての数論』の演習問題をやっていきます．

はじめての数論 原著第4版

問題文

$b_1 < b_2 < \cdots < b_{φ(m)}$ を $1$ と $m$ の間で $m$ と互いに素な整数（$1$ を含む）とし，$B = b_1 b_2 \cdots b_{φ(m)}$ をそれらの積とせよ．この値 $B$ はオイラーの公式の証明に登場した．

問a（前回解いた）の問題文

$B \equiv 1$ $\mod m$ または $B \equiv -1 \mod m$ であることを示せ．

問b の問題文

いくつかの小さな $m$ の値に対して $B$ を計算し，いつ $+1 \mod m$ となり，いつ $-1 \mod m$ となるかのパターンを見つけてみよ．

回答

前回までのあらすじ

前回までのあらすじを軽く書いておきます．

前回は問a を解きました．

$m$ が素数のときには，よく知られたウィルソンの定理から直ちに従います．だからウィルソンの定理のある種の拡張を示しなさいという問題だと考えることができます．

いろいろと試行錯誤した結果，単元群 $G_m := (\mathbb{Z}/ m \mathbb{Z})^{\times}$ が重要だということがわかりました．$G_m$ の位数が２以下の元からなる部分群を $K_m$ とすると，$|K_m|$ はつねに偶数であり，かつ

$$ B \equiv (-1)^{|K_m|/2} \mod m $$

が成り立つことを前回は示しました．

具体例をみる

さて，今回はどうしましょうか．

パターンを見つけてみよという問題ですが，せっかくなので完全に決定しましょう．

まずは前回やった具体例の計算をもう一度見てみましょう．

じっとみてみると，パターンが...パターンが...わかりませんね．

どういうことだってばよ．

中国式剰余定理を使う

いったん具体例を離れて形式的な考察に戻りましょう．

前回「役に立たない」といった中国式剰余定理ですが，今回いろいろ考察したおかげで使えるようになっています．

$m$ が互いに素な数 $a,b$ の積として $m=ab$ と表されていると仮定してみましょう．このとき中国式剰余定理から環として

$$ \mathbb{Z}/ m \mathbb{Z} \cong \mathbb{Z}/ a \mathbb{Z} \times \mathbb{Z}/ b \mathbb{Z} $$

であることが判ります．したがって乗法群として $G_m \cong G_a \times G_b$ であり，$x^ 2 = 1$ かどうかは成分ごとに決まるので $K_m \cong K_a \times K_b$ まで判ります．$K_a$ と $K_b$ の値は $a,b \geq 3$ である限り偶数ですから，大抵の場合 $K_m$ は４の倍数であり，したがって $B \equiv 1 \mod m$ であることが予想されます．

きちんと場合分けをしていきましょう．

• $m$ が素数

  • $m=2$
  • $m$ は奇素数

• $m$ が合成数

  • $m$ の素因数の個数が１
  • $m$ の素因数の個数が２
  • $m$ の素因数の個数が３以上

このように場合分けしてみます．

「$m$ が素数」のケースは既にWilsonの定理によってカタがついていて，$B = -1$ です．

$m$ が合成数のケースを見ていきましょう．素因数の個数が１，つまり何かの素数のベキになっているケースは難しそうなので一旦置いておきます．

「素因数の個数が３以上」の場合には，奇素数が２つ以上含まれていますから $|K_m|$ は確実に４の倍数です．したがって $B=1$ であることがわかります．

「素因数の個数が２」のケースは，$2$ が素因数に含まれているかどうかで変わります．中国式剰余定理によって「素因数の個数が１」のケースに帰着できることは明らかなので，いったん相手にしないことにしましょう．

残るは $m$ が素数ベキであるようなケースのみです．

再び具体例の計算

とりあえず $2$ のベキから始めましょうか．

計算してみるとこんな感じになります．

結構計算が大変ですね．

$x^ 2=1$ となる元を赤い丸で示していますが，隣接していることがわかります．

予想の証明

つまり，次が予想されます．

予想

$m \geq 4$ が２のベキであるとき， $x^ 2 \equiv 1 \mod m$ であることと，$x \equiv \pm 1 \mod m/2$ は同値である．

ちょっとびっくりするような予想ですが，証明していきましょう．これ以上具体例を計算するのはごめんです．

(証明) $x \equiv \pm 1 \mod m/2$ ならば $x^ 2 \equiv 1 \mod m$ であることは明らか．したがって逆方向だけを示せばよい．

$m = 2^ e$ として，$e$ に関する帰納法によって示す．$m = 2^ e$ について予想が成り立つことを $P(m)$ と表すことにする．

$e=2$ のときには明らか．

$e \geq 2$ について $P(m)$ が成り立つと仮定する．その上で $x^ 2 \equiv 1 \mod 2m$ であるような $x$ が与えられたする．

このとき，特に $x^ 2 \equiv 1 \mod m$ が成り立つ．$P(m)$ を仮定したので，$x \equiv \pm 1 \mod m/2$ である．法を $2m$ に持っていくと，これは $x \equiv \pm 1 + mk/2$ (ただし $0 \leq k \leq 3$ )なる $k$ が存在すると言い換えられる．

自乗して $x^ 2 \equiv 1 \pm mk \mod 2m$ を得る．そもそも $x$ は $x^ 2 \equiv 1 \mod 2m$ を満たすものが与えられていたわけだから，$\pm mk \equiv 0 \mod 2m$ である．ゆえに $k$ は偶数でなければならず，$x \equiv \pm 1 \mod m$ がわかる．よって $P(2m)$ が示せた．

これで証明終了．□

証明ができました．

これで $m$ が２の冪であるときの $|K_m|$ の値は完全に決定できます．

• $m=2$ のとき $|K_m| = 1$

• $m=4$ のとき $|K_m| = 2$

• $m \geq 8$ のとき $|K_m| = 4$

です．

あとは $m$ が奇素数 $p$ のベキであるときに $K_m$ を求めればよいだけです．先ほどと同様に具体例を計算してみると，次の予想が立ちます．

予想

$p$ が奇素数であるとき， $x^ 2 \equiv 1 \mod m$ であることと，$x \equiv \pm 1 \mod m$ は同値である．

(証明) これの証明は，先ほどと同様に指数に関する帰納法でできるので省略．□

これにより，$m$ が奇素数のベキであるときには $|K_m| = 2$ であることが判ります．

これによって $B$ の符号は（中国式剰余定理を使うことで）完全に決定できます．

やりました．

感想とまとめ

難しかった演習問題10.1もこれで終わりです．

今回の結果を見ていると，どうやら $B \equiv -1 \mod m$ と単元群が巡回群になることが同値っぽいですね．意外とシンプル？

$2$ のベキの振る舞いが変則的なのがおもしろいです．2乗だからなのかな．

最後の二つの予想の証明ですが，なんとなくp進数っぽい議論だなあと思いました．

関連性があるのかどうかはちょっとわかりません．p進数のこと習ったけど忘れてしまったし．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]