レピュニットと円分体の分解法則 - tsujimotterのノートブック

本日 11/11 はレピュニット（1が続く数）の日ですね。毎年この日が来るとtsujimotterはこちらの記事をTwitterに投稿しています。
tsujimotter.hatenablog.com

この日は数学が好きな人たちの間でも、レピュニット関連の話題がたくさん投稿されるのですが、特に鯵坂もっちょさんのこちらの投稿が気になりました。

11/11ですが pic.twitter.com/6MATw4sGfZ
— 鯵坂もっちょ🐟 (@motcho_tw) 2019年11月11日

レピュニットは

$\underbrace{111\ldots111}_{k \text{ times}}$

とかける数のことですが

$F_{k}(X) = X^{k-1} + X^{k-2} + \cdots + X^2 + X + 1$

という多項式を考えて、 $X = 10$ を代入したもの、だと考えてもいいわけです。

このように考えると、多項式 $F_k(X)$ の既約分解を考えることで、レピュニットの因数分解を得ることができます。たとえば

$F_4(X) = X^3 + X^2 + X + 1 = (X + 1)(X^2 + 1)$

という多項式の既約分解を考えることで、 $X = 10$ と代入してレピュニットの因数分解

$1111 = F_4(10) = 11 \cdot 101$

が得られるというわけですね。

これは面白い見方だと思いました。

一方で、 $F_7(X) = X^6 + X^5 + X^4 + X^3 + X^2 + X + 1$ を考えると、これはよく知られているように $\mathbb{Q}$ 上既約な多項式です。たとえば、証明はこちらに載っています。
biteki-math.hatenablog.com

一般に、素数を $q$ として、 $F_q(X) = X^{q-1} + X^{q-2} + \cdots + X^2 + X + 1$ は既約であることが示せます。

ところで、この $F_7(X)$ に $X = 10$ を代入したレピュニットは、素数にはならず、以下のように素因数分解されます。

$F_7(10) = 1111111 = 239 \times 4649$

すなわち、 $F_k(X)$ が既約だからといって、 $F_k(10)$ が素数であるとは限らないというわけですね。

それはたしかにそうなのですが、もう少し踏み込んだ議論ができないかと思いました。そこでこんなツイートをしたわけです。

この見方は面白いな。円分多項式の既約性と対応づけられないかなと思って考えてました。

一方で、たとえばX^6+X^5+X^4+X^3+X^2+X+1はQ上既約だけど、1111111 = 239 × 4649 と割り切れてしまう。上手い解釈はできないかな。
— tsujimotter ロマ数本好評発売中!! (@tsujimotter) 2019年11月11日

このツイートに対して、梅崎さんと山田さんのお二方から、円分体の分解法則と関連づけられそうだという情報をいただきました。今回は、それをまとめて見たいと思います。

f:id:tsujimotter:20191112010830p:plain:w400

円分体との関係

まず円分体とは、 $k$ を $k > 2$ なる整数として、1の原始 $k$ 乗根 $\zeta_k$ を $\mathbb{Q}$ に添加した体 $\mathbb{Q}(\zeta_k)$ のことです。tsujimotterのノートブックでも度々登場しています。

原始 $k$ 乗根 $\zeta_k$ の最小多項式は、 $k$ が素数のときには $F_k(X)$ に一致します。したがって、以降 $q$ を奇数の素数に固定して

$\mathbb{Q}(\zeta_q) \simeq \mathbb{Q}[X]/(F_q(X))$

という同型があります。

実際、 $F_q(X)$ は円分体 $\mathbb{Q}(\zeta_q)$ の性質に大きく関係しているわけですが、その一つとして素イデアルの分解法則があります。

$\mathbb{Q}$ の整数環 $\mathbb{Z}$ の素イデアルは、素数を $p$ として $(p)$ の形で表せます。素イデアルは $(p)$ は、円分体 $\mathbb{Q}(\zeta_q)$ の整数環 $\mathbb{Z}[\zeta_q]$ の素イデアルに持ち上げることができます。このとき、持ち上げた素イデアル $(p)$ は、 $\mathbb{Z}[\zeta_q]$ でも素イデアルのままとは限りません。

たとえば、 $\mathbb{Q}(\zeta_5)$ の場合、 $\mathbb{Z}$ の素イデアル $(11)$ は

$(11) = (2+\zeta_5)(2+\zeta_5^2)(2+\zeta_5^3)(2+\zeta_5^4) \tag{1}$

のように分解されます。一般に $(p)$ が $\mathbb{Q}(\zeta_q)$ で $q-1$ 個の素イデアルに分解されるとき、 $(p)$ は $\mathbb{Q}(\zeta_q)$ で完全分解するといいます。上の例では、 $(11)$ は $\mathbb{Q}(\zeta_{5})$ で完全分解するというわけですね。

このように、素イデアルが分解する法則のことを、そのまま「素イデアル分解法則」といいます。

円分体の素イデアル分解法則は、類体論等の理論により、よく知られています。ここでは、その帰結だけ紹介しましょう。

円分体の素イデアル分解法則（の一部）

$q$ を奇数の素数とし， $p$ を $p \neq q$ なる素数とする．このとき，以下の同値が成り立つ：
$F_q(X)$ が $\bmod{p}$ で完全分解する（ $F_q(X)$ が $\bmod{p}$ で $q-1$ 個の相異なる多項式の積に分解する）
$\Longleftrightarrow \; (p)$ が $\mathbb{Q}(\zeta_q)$ で完全分解する
$\Longleftrightarrow \; p \equiv 1 \pmod{q}$

特に最後の条件 $p \equiv 1 \pmod{q}$ は非常にわかりやすい条件になっていますね。 $p = 11, \; q = 5$ とすると、式 $(1)$ のケースが、この条件を満たしていることを確認できますね。

さて、レピュニットの話に戻しましょう。

$p \equiv 1 \pmod{q}$ のとき、上記の分解法則から $(p)$ が $\mathbb{Q}(\zeta_q)$ で完全分解することがわかります。

また、このとき $F_q(X) = X^{q-1} + \cdots + X + 1$ が $\bmod{p}$ で完全分解することもわかります。すなわち

$F_q(X) \equiv 0 \pmod{p}$

は、 $q-1$ 個の相異なる解 $X_1, \cdots, X_{q-1}$ を持つことになります。（ $\mod{p}$ で考えています）

このとき $1\leq i \leq q-1$ に対して

$F_{q}(X_i) \equiv 0 \pmod{p}$

が成り立つわけですが、これは $X_i$ 進法のレピュニット

$F_q(X_i) = {\underbrace{111\ldots 111_{(X_i)}}_{q \text{ times}}}$

が、 $\bmod{p}$ で 0 に合同、すなわち $p$ で割り切れるということを表しています。すなわち、レピュニットの素因数を見つけることができたというわけですね。

実際、 $F_7(10) = 1111111 = 239 \times 4649$ のケースを考えると

$239 \equiv 1 \pmod{7}$

$4649 \equiv 1 \pmod{7}$

なので、 $(239), (4649)$ はどちらも $\mathbb{Q}(\zeta_7)$ で完全分解します。また

$F_7(X) \pmod{239}, \; F_7(X) \pmod{4649}$

はどちらも完全分解するわけですが、そのときの共通の解として $X = 10$ が取れたというわけですね。面白い。

他の例を考えてみよう

たとえば、 $100$ 以下では、 $p \equiv 1 \pmod{7}$ なる素数は $29, 43, 71$ の３つです。これらについて、 $\bmod{7}$ での $F_7(X)$ の分解を考えましょう。

sagemathを使って次のようなコードで検証します。

p=2
while p<100:
    p=next_prime(p)
    if p % 7 == 1:
        F=FiniteField(p)
        R.<x>=F[]
        f=factor(x^6+x^5+x^4+x^3+x^2+x+1)
        print p,f

すると次のような結果が得られました。

29 (x + 4) * (x + 5) * (x + 6) * (x + 9) * (x + 13) * (x + 22)
43 (x + 2) * (x + 8) * (x + 22) * (x + 27) * (x + 32) * (x + 39)
71 (x + 23) * (x + 26) * (x + 34) * (x + 39) * (x + 41) * (x + 51)

すなわち、 $\bmod{29}$ においては

$F_7(X) \equiv (X + 4) (X + 5) (X + 6) (X + 9) (X + 13) (X + 22) \pmod{29}$

が成り立つということですね。符号を反転した方が解釈しやすいので

$F_7(X) \equiv (X - 25) (X - 24) (X - 23) (X - 20) (X - 16) (X - 7) \pmod{29}$

としておきます。すると、 $F_7(X) \equiv 0 \pmod{29}$ の解は

$X \equiv 7, 16, 20, 23, 24, 25 \pmod{29}$

となるわけですね。

よって、先ほどの議論により $\bmod{29}$ で $7, 16, 20, 23, 24, 25$ に合同な $X$ 進法の $7$ 桁のレピュニットは $29$ で割り切れるというわけです。

実際計算してみると

$1111111_{(7)} = 137257 = 29 \times 4733$

$1111111_{(16)} = 17895697 = 29 \times 43 \times 113 \times 127$

$1111111_{(20)} = 67368421 = 29 \times 71 \times 32719$

$1111111_{(23)} = 154764793 = 29 \times 5336717$

$1111111_{(24)} = 199411801 = 29 \times 239 \times 28771$

$1111111_{(25)} = 254313151 = 29 \times 449 \times 19531$

となり、たしかにすべて素因数として $29$ を持つことがわかりますね。

惰性する場合

（私の勘違いがあったため、この節の内容は大幅に修正しました）

上の話では $F_q(X)$ が $\bmod{p}$ で完全分解するケースだけを考慮していました。完全分解しないケースについてはどうでしょうか？

完全分解しない場合は、たとえば $p = 13, \; q = 7$ のケース

$F_7(X) \equiv (X^2 + 3X + 1) (X^2 + 5X + 1) (X^2 + 6X + 1) \pmod{13}$

のように、各多項式の次数が 2 以上になります。また、ガロア拡大における素イデアル分解の性質により、分解された多項式の次数はすべて等しくなります。よって、このようなケースでは $F_q(X)$ は $\bmod{p}$ で解を持たないということになります。（もし解を持つなら、1次の多項式の積に分解されるため）

完全分解しない素数、すなわち $p\neq q$ かつ $p \not \equiv 1 \pmod{q}$ においては、 $p$ が $F_q(X)$ を割り切るような $X$ 進法が存在しないということになりますね。

$p = 13, \; q = 7$ の例で考えると、どんな $X$ 進法に対しても

$1111111_{(X)}$

は $13$ で割り切れない、ということになるでしょうか。

この辺の議論はちょっと自信がないのですが、もし成り立つなら面白い結論です。すなわち、 $q$ 桁のレピュニットの素因数として、 $p \not \equiv 0, 1 \pmod{q}$ なる素数 $p$ は現れないということになります。本当でしょうか。

実際、素数 $q$ 桁のレピュニットの素因数分解の様子を確認すると、たしかに $q = 3, p = 3$ のとき（ $p = q$ ）を除けば、 $p \equiv 1 \pmod{q}$ 型の素因数になっていますね。

111 = 3 * 37
11111 = 41 * 271
1111111 = 239 * 4649
11111111111 = 21649 * 513239
1111111111111 = 53 * 79 * 265371653

おわりに

今回は円分体の素イデアル分解法則が、レピュニットの素因数に関連するというお話をしました。

円分体の理論は好きで、たびたび記事にしていますが、このような形で役にたつ（？）とは思っていなかったので、とても新鮮でした。アイデアをくださった梅崎さん、山田さんありがとうございました。

それでは今日はこの辺で。