流れる空の中で数学を。

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

マスターデーモンがついに解けました

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

整数論の絶版本・品切れ本をコチラから購入できます!

追記(2018/07/25):計算ミスがあり、証明も冗長だったので、少し修正しました。

マスターデーモン

 マスターデーモンとは、1990年IMO中国大会の第3問で出題された次の問題である。

「2以上の自然数n
\frac{2^n+1}{n^2}……(1)
が整数となるものを全て求めよ。」

 この問題、かなり前に挑戦したが、解けなくてしばらく放置していた。 

sky-time-math.hatenablog.jp


 ひさびさに問題を見てみるとなんだか解ける感触がしたので、やってみたらついに解けました。そこで、今回は自分がたどり着いた解法を記事にまとめておきます。フェルマーの小定理合同式さえしっていれば、普通の高校生でも理解できるように書いたつもりです。最近暑くて頭の回転が鈍っているので、うっかりどこかを間違えているかもしれませんが、そのときは優しく指摘してくれると助かります。

追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムも作りました。興味がある方は以下の記事を参考にしてください。

sky-time-math.hatenablog.jp

 

 

解答のアウトライン

 nが偶数なら、与式の分母が偶数、分子が奇数となるので題意の式は整数にならない。以後、nは奇数とする。
 n=3が求める解の内の一つであることはすぐにわかる。そして、解がこれしかないことを示したい。
 今回、自分が使ったアプローチは「因数分解」による方法だ。
nがある素因数p( \ge 3)k(\ge 1)個もつとき、すなわちn=p^k N(Nは奇数で、Npは互いに素。)とあらわせるとき、r^n+1は次の形に因数分解できる。(r自然数)

r^n+1=(r+1) \cdot \frac{r^p+1}{r+1} \cdot \frac{r^{p^2}+1}{r^p+1} \cdots \frac{r^{p^k}+1}{r^{p^{k-1}}+1}\cdot \frac{r^{p^{k} N}+1 }{r^{p^k}+1} ……(2)

といっても、このままでは見づらいので、少し記号を用意する。mを奇数、x自然数とするとき、自然数f_m(x)

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

とおくと、(2)式は次のように書き直せる。

r^n+1=(r+1) f_p(r) \cdot f_p(r^p) \cdot f_p(r^{p^2}) \cdots f_p(r^{p^{k-1}}) \cdot f_N(r^{p^k})……(4)

このような因数分解nの各素因子ごとに存在するので、これをうまく使って問題を解いていく。証明は、次の2つのパートに分かれる

nに素因数3がいくつ含まれるか?
n=3^kNと表される場合を考えて、(4)式でr=2,p=3とすると、f_p(r^{p^l})(l=0,1,2,\cdots,k)が3でちょうど一回だけ割れることを示す。そのことから、2^n+1が素因数3k+1個だけ持つことがわかる。分母には素因子32k個現れるので、n=3^kNに現れる指数はk=0,1でなければならないことがわかる。

n3より大きい素因数を持たないこと。
n3の次に大きい素因子pを持つと仮定として、その指数をmとする。つまり、n=3^k p^m M(k=0,1)と表せる場合を考える。このとき、8\equiv 1 (\bmod 7)のため、k=1の場合、

2^n+1\equiv 8^{p^m M}+1 \equiv 2 \not\equiv 0 (\bmod 7)

よって、k=1の場合、(1)式の分子は7の倍数ではないので、n7を素因数に持たない。
 最後に、2^n+1\equiv 8^{p^m M}+1が素因数pを持たないことを背理法により示す。

 ①②から、題意を満たすn3のみであることがわかる。

nに素因数3がいくつ含まれるか?

n=3^kNと表される場合を考える。(4)式でr=2,p=3l=0,1,2,\cdots,kとして、

f_p(r^{p^l})=f_3(2^{3^l})=1-2^{3^l}+2^{2\cdot 3^l}……(5)

ここで、2 \equiv -1 (\bmod 3)より、

f_p(r^{p^l}) \equiv 1-(-1)^{3^l}+(-1)^{2\cdot 3^l} \equiv 1+1+1 \equiv 0 (\bmod 3)

また、9=3^2を法として考えると、
f_p(r)=1-2+4 =3 \not\equiv 0 (\bmod 9)……(6)

であり、l=1,2,\cdots,kとして、
f_p(r^{p^l})=1-2^{3^l}+2^{2\cdot 3^l}=1-8^{3^{l-1}}+8^{2\cdot3^{l-1}}……(7)

であるが、8\equiv -1 (\bmod 9)なので、

f_p(r^{p^l}) \equiv 1-(-1)^{3^{l-1}}+(-1)^{2\cdot3^{l-1}} =1 +1+1 =3 \not\equiv 0 (\bmod 9)……(8)

従って、f_p(r^{p^l})は素因数3をちょうど1つだけ持つ。

 続いて、f_N(r^{p^k})3で割れないことを確認する。

f_N(r^{p^k})=f_N(2^{3^k})=1-2^{3^k}+2^{2 \cdot 3^k} - \cdots + 2^{(N-1) \cdot 3^k}……(9)

再び、2 \equiv -1 (\bmod 3)なので、

f_N(r^{p^k}) \equiv 1 - (-1)^{3^k} + \cdots +(-1)^{(N-1)\cdot 3^k} (\bmod 3)
\equiv 1+1+\cdots+1=N (\bmod 3)……(10)

ところで、N3と互いに素なので、N3の倍数でない。よって、

f_N(r^{p^k}) \equiv N \not\equiv 0 (\bmod 3)……(11)

以上より、(4)式でr=2,p=3とすることで、2^n+1は素因数3k+1個持つことがわかった。したがって、分母に現れる素因数3の個数が2k個なので、(1)式が整数となるためには、

k+1 \ge 2k
k =0,1……(12)

でなければならないことがわかった。よって、題意を満たすnn=3^k N(k=0,1)と表せる。

n3より大きい素因数を持たないこと

 n3の次に大きい素因子pを持つと仮定として、その指数をmとする。つまり、

n=3^k p^m M(k=0,1)……(13)

と表せる場合を考える。ここで、解答のアウトラインで書いたように、k=1のとき、p7ではない。

p \neq 7……(14)

2^n+1pを素因数に持たないことを示したい背理法で示したいので、2^n+1pで割り切れたと仮定する。まず

R=2^{3^k}……(15)

とおくと、k=0,1なので、

R=2,8……(16)

である。法をpとしてフェルマーの小定理を使うと、R^p\equiv R(\bmod p)なので、

2^n+1=R^{p^m M}+1\equiv R^M+1 (\bmod p)……(17)

となる。仮定より、2^n+1\equiv 0(\bmod p)なので、

R^M +1 \equiv 0  (\bmod p)……(18)
R^{2M}\equiv 1 (\bmod p)……(19)

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

R^{p-1}\equiv 1 (\bmod p)……(20)

であった。ここで、

R^{\mu}\equiv 1(\bmod p) ……(21)

が成り立つ最小の自然数\muとすると、(19),(20)式より、ある自然数s,tが存在して、

2M=s \mu……(22)
p-1=t \mu……(23)

と表せる。(22)式の両辺にtをかけると、

2Mt=s (p-1)……(24)

ここで、(13)式に戻り、Mの定義に立ち戻ると、Mの素因子はすべて p (\gt p-1)より大きいか、またはM=1なので、(24)式からある自然数uが存在して、

s=Mu……(25)

となる。これを(22)式に代入して整理すると、

2=u \mu……(26)

従って、

\mu=1,2……(27)

である。(16)式よりR=2,8であったので、

(i)R=2の場合、(21)式から

2 \equiv 1 (\bmod p)または2^2 \equiv 1(\bmod p)

\Rightarrow 1\equiv 0(\bmod p)または3 \equiv 0 (\bmod p)……(28)

となるが、これを満たす素数p (\ge 5)は存在しないので矛盾。

(ii)R=8の場合も、(21)式から

8 \equiv 1(\bmod p)または8^2 \equiv 1 (\bmod p)

\Rightarrow 7\equiv 0(\bmod p)または63 =3^2\times7 \equiv 0 (\bmod p)……(29)

となる。これを満たす素数p (\ge 5)7のみであるが、R=8のときk=1であり、この場合、(14)式に書いたようにp\neq 7なので矛盾。

 以上より、背理法の仮定が偽であることが言えたので、

2^n+1pで割れないことが示された

 以上より、n3より大きな素因数を持つとすると、2^n+1pで割れきれず、(1)式の分母n^2が素因数pを持つので、(1)式は整数にならない。従って、n3より大きい素因数を持たない。

よって、(1)式が整数になるような整数n (\ge 2)は、n=3に限ることが言えた。