マスターデーモンがついに解けました - 流れる空の中で数学を。

追記(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$ は奇数で、 $N$ と $p$ は互いに素。)とあらわせるとき、 $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$ の各素因子ごとに存在するので、これをうまく使って問題を解いていく。証明は、次の２つのパートに分かれる。

① $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$ が素因数 $3$ を $k+1$ 個だけ持つことがわかる。分母には素因子 $3$ が $2k$ 個現れるので、 $n=3^kN$ に現れる指数は $k=0,1$ でなければならないことがわかる。

② $n$ が $3$ より大きい素因数を持たないこと。
$n$ が $3$ の次に大きい素因子 $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の倍数ではないので、 $n$ は $7$ を素因数に持たない。
　最後に、 $2^n+1\equiv 8^{p^m M}+1$ が素因数 $p$ を持たないことを背理法により示す。

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

① $n$ に素因数 $3$ がいくつ含まれるか？

$n=3^kN$ と表される場合を考える。(4)式で $r=2$ , $p=3$ 、 $l=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$ をちょうど１つだけ持つ。

続いて、 $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)

ところで、 $N$ は $3$ と互いに素なので、 $N$ は $3$ の倍数でない。よって、

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

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

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

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

② $n$ が $3$ より大きい素因数を持たないこと

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

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

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

$p \neq 7$ ……(14)

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

$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+1$ は $p$ で割れないことが示された。

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

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

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

マスターデーモン

「2以上の自然数で……(1)が整数となるものを全て求めよ。」

解答のアウトライン

①に素因数がいくつ含まれるか？

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

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

① $n$ に素因数 $3$ がいくつ含まれるか？

② $n$ が $3$ より大きい素因数を持たないこと