【解の構成方法】マスターデーモンの一般化

マスターデーモンの一般化

　今回の記事では、マスターデーモンの一般化について考える。
「自然数rが与えられたとき、２以上の $n$ で
$\frac{r^n+1}{n^2}$ ……(1)
が整数となるものを全て求めよ。」

　結論から言うと、(1)式が整数になるような任意の $n$ を構成するアルゴリズムを求めることはできた。ところが、一般の自然数 $r$ に対して、 $n$ を一般的に表す公式を求めるのは極めて困難である。そのため、(1)式を満たす解が無限に存在するかどうかすらも難しい。この難しさは、素因数分解の難しさに関連するものなので、相当な「武器」を持ってこないと太刀打ちできないだろう。
　また、この記事では、自然数は $1$ 以上の整数であるとする。

今回の話のアウトライン

今回の記事のアウトラインは、次の通りである。

①: $n$ が偶数にならないこと
②: $n$ の最小の素因数が、 $r+1$ の奇数の素因数のいずれかに一致すること
③: $n$ の最小の素因数の指数は、 $r+1$ の対応する素因数の指数以下であること
④と⑤:③の証明
⑥:一般化されたマスターデーモンの解を構成するアルゴリズム

①②③を繰り返し用いることで、(1)式が整数になる $n$ を構成するアルゴリズムが得られる。

① $n$ が偶数にならないこと

　 $r$ が偶数のときは、(1)式の分子が奇数になるので、(1)式の分母は偶数ではない。よって、 $n$ も偶数でない。
　 $r$ が奇数の時、 $n$ が偶数と仮定する。すると、(1)式の分母は $4$ の倍数になるので、(1)式が整数になるなら分子 $r^n+1$ も $4$ の倍数である。従って、

$r^n+1\equiv 0 (\bmod 4)$ ……(2)

　ところが、 $r$ は奇数なので、

$r\equiv \pm 1 (\bmod 4)$ ……(3)

であるので、これを(2)式に代入すると、 $n$ を偶数と仮定したことから、

$(\pm 1)^n+1 \equiv 1+1 \equiv 2$
$\therefore 2 \equiv 0 (\bmod 4)$ ……(4)
となるので、矛盾である。背理法により、 $r$ が奇数のときも、 $n$ は偶数ではない。
　よって、(1)式が整数になるならば、 $n$ は偶数ではない。

② $n$ の最小の素因数が、 $r+1$ の奇数の素因数のいずれかに一致すること

　 $n(\ge 2)$ の最小の素因数を $q$ とし、その指数を $k$ とする。すると、 $n$ は、 $p$ と互いに素な自然数 $N$ を用いて、

$n=q^k N$ ……(5)

と表せる。(1)式の分母が $q$ の倍数になるので、

$r^n+1\equiv 0 (\bmod q)$ ……(6)

である必要がある。フェルマーの小定理より、

$r^n+1\equiv r^{q^k N}+1 \equiv r^N +1 \equiv 0 (\bmod q)$ ……(8)
$r^{2N}\equiv 1(\bmod q)$ ……(9)

また、フェルマーの小定理より、

$r^{q-1}\equiv 1 (\bmod q)$ ……(10)

ここで、法を $q$ としたときの $r$ の位数は、 $\gcd(2N,q-1)$ の約数になるが、 $N$ は $q$ より小さい素因数を持たないので、

$\gcd(2N,q-1)=2$ ……(11)

である。よって、

$r\equiv 1 (\bmod q)$ または $r^2\equiv 1(\bmod q)$
$\iff r\equiv \pm 1(\bmod q)$ ……(12)

である。 $r \equiv 1(\bmod q)$ とすると、(8)式より、

$1^N+1\equiv 2 \equiv 0 (\bmod q)$ ……(13)

となるので矛盾である。従って、

$r\equiv -1 (\bmod q)$
$\therefore r+1 \equiv 0(\bmod q)$ ……(14)

である。
　よって、 $n$ の最小の素因数 $q$ は、 $r+1$ の奇数の素因数のいずれかに一致する。

③ $n$ の最小の素因数の指数は、 $r+1$ の対応する素因数の指数以下であること

　 $r+1$ が次のように素因数分解されたとする。

$r+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(15)

ここで、 $t$ は１以上のある自然数で、 $e_j(j=0,1,\cdots,t)$ は０以上の整数で、 $e_j$ の内少なくとも１つは $0$ ではない。

　②より、 $n$ の最小の素因数は、ある $j(=1,2,\cdots,t)$ に対して

$q=p_j$ ……(16)
である。 $n=q^k N$ なので、 $r^n$ は次の形に因数分解できる。

$r^{q^k N}+1=(r+1)f_q(r)f_q(r^q)f_q(r^{q^2}) \cdots f_q(r^{q^{k-1}})f_N(r^{q^k})$ ……(17)

ここで、 $f_m(x)$ は、奇数 $m$ に対して、

$f_m(x)=\frac{r^m+1}{r+1}=1-r+r^2-\cdots+ r^{m-1}$ ……(18)

と定義している。このように因数分解したとき、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv 0 (\bmod q)$ ……(19)
$f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ ……(20)
$f_N(r^{q^k})\not\equiv 0 (\bmod q)$ ……(21)

であることが示せる(後で、④,⑤で示す)。従って、 $f_q(r^{q^j})$ は、 $q$ でちょうど１回だけ割り切れるので、(15),(17)式より、

$r^n+1$ は $q=p_j$ で $e_j+k$ 回だけ割り切れる……(22)

(1)式の分母は、 $q$ で $2k$ 回割り切れるので、(1)式が整数であるためには、

$e_j+k \ge 2k$
$\iff k \le e_j$
$\therefore k=1,2,\cdots, e_j$ ……(23)

である必要がある。
　特に、
$n=q^k(k=1,2,\cdots,e_j)$

は一般化されたマスターデーモンの１つの解となっている。
　それでは、(19),(20),(21)式を示そう。

④ $f_q(r^{q^j})\equiv 0 (\bmod q)$ 、 $f_N(r^{q^k})\not\equiv 0 (\bmod q)$ であること

　フェルマーの小定理より、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv f_q(r) (\bmod q)$ ……(24)
$f_N(r^{q^k})\equiv f_N(r) (\bmod q)$ ……(25)

である。(14),(18)式より、 $N$ と $q$ が互いに素であることに注意して、

$f_q(r)\equiv 1-(-1)+(-1)^2-\cdots (-1)^{q-1}\equiv q \equiv 0 (\bmod q)$ ……(26)
$f_N(r)\equiv 1-(-1)+(-1)^2-\cdots (-1)^{N-1}\equiv N \not\equiv 0 (\bmod q)$ ……(27)

よって、(19),(21)式が成立する。

⑤ $f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ であること

　まず、 $r+1\equiv 0 (\bmod q)$ より、

$(r+1)^2\equiv r^2+2r+1\equiv 0 (\bmod q^2)$
$r^2 \equiv -2r-1 (\bmod q^2)$ ……(28)

であるので、 $q$ を法とするとき、 $f_q(r^{q^j}$ は $r$ の１次式で表せることに着目する。 $j$ を自然数とするとき、

$r^j \equiv a_j r + b_j$ ……(29)

と置くと、(29)式に $r$ をかけて、(28)式を用いることで、 $a_j,b_j$ の漸化式を得る。

$a_{j+1}=b_j-2a_j$ ……(30)
$b_{j+1}=-a_j$ ……(31)

(31)式を(30)式に用いて、

$a_{j+1}=-2a_j -a_{j-1}$ ……(32)

となるので、 $a_j$ の一般解は、

$a_j=(-1)^j(\alpha j +\beta)$ ……(33)

と表せる。 $a_1=1,a_2=-2$ となることから、 $\alpha,\beta$ を求めた後、

$a_j=(-1)^{j+1} j$ ……(34)
$b_j=(-1)^{j-1}(j-1)$ ……(35)

を得る。これより、

$f_q(r)=1+\sum_{j=1}^{q-1} r^j$
$\equiv 1-(\sum_{j=1}^{q-1} (-1)^j j)r +(\sum_{j=1}^{q-1} (-1)^{j-1} (j-1)) (\bmod q^2)$
$\equiv \frac{1-q}{2} r + \frac{3-q}{2}$ ……(36)

ここで、 $f_q(r)\equiv 0 (\bmod q^2)$ と仮定すると、

$\frac{1-q}{2} r + \frac{3-q}{2} \equiv 0 (\bmod q^2)$
$q(1-q)r - q(q-3) \equiv 0(\bmod q^2)$
$q (r+3) \equiv 0 (\bmod q^2)$
$\therefore r\equiv -3 (\bmod q)$ ……(37)

となるが、 $r\equiv -1 (\bmod q)$ であったので矛盾。よって、

$f_q(r)\not\equiv 0 (\bmod q^2)$ ……(38)

　次にオイラーの定理より*1、

$r^{\varphi(q^2)}\equiv r^{q(q-1)} \equiv1(\bmod q^2)$
$\therefore r^{q^2}\equiv r^q (\bmod q^2)$ ……(39)

であるので、

$j=1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv f_q(r^q) (\bmod q^2)$ ……(40)

が言えるので、 $f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ を示すには、

$f_q(r^q) \not\equiv 0 (\bmod q^2)$ ……(41)

を示せば十分である。 $f_q(r)\not\equiv 0 (\bmod q^2)$ を示したときと同様にして、

$f_q(r^q)\equiv - \frac{q^2-q}{2} r - \frac{q^2-q-2}{2} (\bmod q^2)$ ……(42)

を得る。 $f_q(r^q) \equiv 0 (\bmod q^2)$ となったと仮定すると、(42)式に $2$ をかけて、

$(-q^2+q)r \equiv q^2 -q -2 (\bmod q^2)$
$qr \equiv -q-2 (\bmod q^2)$
$0\equiv q^2 r \equiv -2q$
$\therefore 2q\equiv 0 (\bmod q^2)$ ……(43)

これを満たす奇素数 $q$ は存在しないので、矛盾。よって、

$f_q(r^q)\not\equiv 0 (\bmod q^2)$ ……(44)

　以上をまとめて、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j}) \not\equiv 0 (\bmod q^2)$ ……(45)

が示せた。

⑥:一般化されたマスターデーモンの解を構成するアルゴリズム

　①～③を繰り返し用いることにより、一般化されたマスターデーモンの解を構成するアルゴリズムが得られる。

$r_1=r$ とおき、(15)式のように、
$r_1+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(46)
と素因数分解できたとき、ある $p_j$ を１つとり、

$q_1=p_j$ ……(47)

とおく。すると、①～③より、次の $e_j$ 個の自然数は一般化されたマスターデーモンの解になる。

$n=n_1=q_1^{k_1} (k_1=1,2,\cdots,e_j)$ ……(48)

ここで、(48)式のそれぞれの解に対して、

$r_2=r_1^{q_1^{k_1}}$ ……(49)

とおく。

　ここまでを最初のステップとして、一般化されたマスターデーモンの全ての一般解は、以下のようなアルゴリズムにより構成できる。

　 $r_m(m \ge 1)$ が与えられ、

$r_m+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(50)

と素因数分解できたする。(ここでは、式の見やすさの便宜上、(46)式と同じ記号 $p_j,e_j$ を用いているだけで、(50)(51)式の素因数とその指数は(46)式とは別に定まるものである。そして、以下に現れる $p_j,e_j$ は全て(50)式のものである。)

　このとき、 $p_j \gt q_{n-1}$ となる素因数を1つ選び、

$q_{m+1}=p_j$ ……(51)

とおく。そして、 $k_{m+1}=1,2,\cdots,e_j$ に対して、

$n=n_{m+1}=n_m q_{m+1}^{k_{m+1}}$ ……(52)

とおく。すると、

$r^{n_m q_m^{k_{m+1}}}\equiv -1 \; (\bmod q_m)$

であれば、①～③より、(52)式で構成される全ての $n$ は一般化されたマスターデーモンの解となる。
　最後に、

$r_{m+1}=(r_m)^{q_{m+1}^{k_{m+1}}}$ ……(53)

とおき、同じアルゴリズムを繰り返すことで、一般化されたマスターデーモンの全ての解が得られる。(このことは、rを(53)式で繰り返し与え直して、①～③を繰り返し適用できることからわかる。)
　このアルゴリズムが有限回で終われば、一般化されたマスターデーモンは有限個の解しか持たない。このアルゴリズムが有限回で終わるためには、 $k_1,k_2,\cdots$ のあらゆ取り方によって構成され得る任意の自然数の系列