流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

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

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

 今回の記事では、マスターデーモンの一般化について考える。
自然数rが与えられたとき、2以上の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+14の倍数である。従って、

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)の約数になるが、Nqより小さい素因数を持たないので、

\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は1以上のある自然数で、e_j(j=0,1,\cdots,t)は0以上の整数で、e_jの内少なくとも1つは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でちょうど1回だけ割り切れるので、(15),(17)式より、

r^n+1q=p_je_j+k回だけ割り切れる……(22)

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

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

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

は一般化されたマスターデーモンの1つの解となっている。
 それでは、(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)式より、Nqが互いに素であることに注意して、

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の1次式で表せることに着目する。j自然数とするとき、

r^j=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)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) - 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)

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

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を1つとり、

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)式の素因数とその指数は(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)

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

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

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

r_1+1,r_2+1,\cdots,r_m+1,\cdots……(54)

に現れる素因数の種類が有限であればいい。(これは素因数分解を前提にした話になっているので、これ以上立ち入って一般論を展開するのはかなり困難だと思う。)

 特に、r=2のときは、

2+1=3
2^3+1=9=3^2

となるので、上記のアルゴリズムは1回目で終了し、r=2のときの解が3しか存在しないことがわかる。他にもいくつかのrで試してみる。

  r=3の場合は、

r+1=4=2^2

なので、解は存在しない。

 r=4の場合は、

4+1=5
4^5+1=1025=5^2\times 41

より、n=5,205(=5\times41)などが解になるが、(54)式の系列に現れる素因数の種類が有限であるかは自明でないので、解の個数も自明ではない。

 r=5の場合は、

5+1=6=2 \times 3
5^3+1=126=2\times 3^2 \times 7

より、n=3,21(=3\times 7)などが解になるが、これもまた、(54)式の系列に現れる素因数の種類が有限であるかは自明でないので、解の個数も自明ではない。

 r=20の場合も考えてみると、

20+1=21=3\times 7

より、n=3,7などが解になることがわかる。この場合も解の個数は非自明である。

 最後に、以上のアルゴリズムから次の系が導かれることを指摘しておく。

(i) r+1が奇数の素因子を持たないとき、一般化されたマスターデーモンは解を待たない。
(ii) r+1が奇数の素因子を持つとき一般化されたマスターデーモンは解を持ち、そのうち最小の解は、r+1の最小の奇数の素因子pに一致する。