「マスターデーモン」とその一般化
1990年の数学オリンピックに出題された次の問題は「マスターデーモン」として広く知られています。
整数 $n\geq 2$ で、$\frac{2^n+1}{n^2}$ が整数となるものをすべて求めよ。
先日twitterでFoxQ氏がこの変形とも言える問題を出題し、先日の数学デーでもこの問題が話題となりました。
これについては、$19$ の倍数を含めても解は $n=3$ しかないことがわかります。
次のエントリにFoxQ氏による解答があります。
sky-time-math.hatenablog.jp
これらの問題は次のように一般化されます。
$r\geq 2, k\geq 1$ を整数とする。
整数 $n\geq 2$ で、$\frac{r^n+1}{n^k}$ が整数となるものをすべて求めよ。
FoxQ氏は「マスターデーモン」とその一般化について考察する記事をいくつか書いています。
sky-time-math.hatenablog.jp
sky-time-math.hatenablog.jp
FoxQ氏は一般化された「マスターデーモン」の解を得るアルゴリズムを構成していますが、
本記事では、見方を変えてある整数 $n\geq 2$ が一般化された「マスターデーモン」の解であるかを
判定する方法を考えることからこの問題を考察したいと思います。
$r^N+1$ の形の数を割り切る $p$ の指数
この問題を解くために、一般的に与えられた正の整数 $N$ と素数 $p$ について $r^N+1$ の形の数を割り切る $p$ の指数
（$x$ を割り切る $p$ の指数とは、 $p^e$ が $x$ を割り切る最大の指数 $e$ を指します）を求めたいわけですが、
出発点となるのは、まず、$r^N-1$ を割り切る $p$ の指数に関する次の一般的な事実です。
指数持ち上げ補題
$l$ を $p$ を法とする $r$ の（乗法）位数とする。
$e$ を $N$ を割り切る $p$ の指数とし
$N=lp^e m$ とおく。
$f$ を $r^l-1$ を割り切る $p$ の指数とおくと
$r^N-1$ を割り切る $p$ の指数は $f+e$ に一致する。
この補題は Nagell, Introduction to number theory, Theorems 94-95 や
Shapiro, Introduction to the theory of numbers, Lemma 6. 4A. 2 などにあります。
なお最近は指数持ち上げ補題あるいは LTE (Lifting The Exponent) と呼ばれているようです。
$L=lp^e$ とおくと $N=Lm$ より
\begin{equation}\label{eq11}
\frac{r^N-1}{r^L-1}=r^{(m-1)L}+r^{(m-2)L}+\cdots +1\equiv m\pmod{p},
\end{equation}
$\gcd(m, p)=1$ だから、この左辺は $p$ では割り切れません。
各 $s$ に対し $r^{lp^s}-1$ を割り切る $p$ の指数を $f_s$ とし
$r^{lp^s}-1=A_s p^{f_s}$ とおくと
\begin{equation}
r^{lp^{s+1}}=(A_s p^{f_s}+1)^p=1+pA_s p^{f_s}+\frac{p(p-1)}{2} A_s p^{2f_s}+\cdots\equiv 1+A_s p^{f_s+1} \pmod{p^{2f_s+1}}
\end{equation}
となりますが $2f_s+1>f_s+1, \gcd(A_s, p)=1$ ですから
$r^{lp^{s+1}}-1$ を割り切る $p$ の指数は $f_s+1$ と一致します。よって
$f_{s+1}=f_s+1$ がつねに成り立ちますから
\begin{equation}\label{eq12}
f_e=f_0+e=f+e
\end{equation}
が成り立ちます。$(\ref{eq11}), (\ref{eq12})$ から
$r^N-1$ を割り切る $p$ の指数は $f+e$ に一致することがわかります。
このことから、一般的に与えられた正の整数 $N$ と素数 $p$ について $r^N+1$ を割り切る $p$ の指数について
次の一般的な事実が導かれます。
$r^N+1$ を割り切る素数に対する指数公式
奇素数 $p$ が $r^N+1$ を割り切るとき
$p$ を法とする $r$ の位数は偶数でなければならず、
$p$ を法とする $r$ の位数を $2l$ とすると
$N$ は $l$ の奇数倍である。
逆に $N$ が $l$ の奇数倍ならば $p$ は $r^N+1$ を割り切る。
このとき、 $e$ を $N$ を割り切る $p$ の指数、$N=lp^e m$ とし、
$f$ を $r^l+1$ を割り切る $p$ の指数とおくと
$r^N+1$ を割り切る $p$ の指数は $f+e$ に一致する。
$p$ を法とする $r$ の位数を $o$ とおきます。
$p$ が $r^N+1$ を割り切るならば $r^{2N}-1$ を割り切るので
以前、Fermatの小定理と乗法位数について触れたことから
$2N$ は $o$ の倍数です。
ここで $N$ が $o$ の倍数とすると
$p$ が $r^N-1$ を割り切るので $p$ は $(r^N+1)-(r^N-1)=2$ も割り切るので $p=2$ となって
$p$ が奇数としたことに反します。
$o$ が奇数のとき $N$ も $o$ の倍数なので
よって $o=2l$ は偶数でなければならず、
$2N$ はその倍数ですから $N$ は $l$ の倍数です。
$N$ が $l$ の偶数倍のとき $N$ は $o=2l$ の倍数なので、
$N$ が $l$ の奇数倍でなけれないけません。
逆に $N$ が $l$ の奇数倍ならば、$N=(2m+1)l$ とおくと
$r^N+1=(r^l+1)(r^{2ml}-r^{2(m-1)l}+\cdots -r^l+1)$ は $r^l+1$ の倍数なので
$p$ の倍数です。
さて $f^\prime$ を $r^{2l}-1$ を割り切る $p$ の指数とおくと
先程の指数持ち上げ補題より $r^{2N}-1$ を割り切る $p$ の指数は $f^\prime+e$ と一致します。
$p$ が $r^N-1$ を割り切るとすると $p$ は奇数なので $r^N+1=(r^N-1)+2$ を割り切らなくなります。
よって $p$ は $r^N-1$ を割り切らず、 $r^l-1$ も割り切りません。
よって $f=f^\prime$ かつ $r^N+1$ を割り切る $p$ の指数は $f^\prime+e=f+e$ と一致します。
一般化された「マスターデーモン」の解の判定法
上記の指数公式を使うと、与えられた整数 $n$ が一般化された「マスターデーモン」の解
であるかどうか判定することができます。
まず $n$ が偶数のとき、 $n^2$ は $4$ の倍数ですが
$r^n+1$ は $r$ が偶数のとき奇数か、$r$ が奇数のとき（$r^n\equiv 1\pmod{4}$ なので）
いずれの場合でも $2$の奇数倍なので $n^2$ で割り切れません。
よって $n$ は奇数でなければいけません。
$n=\prod_{i=1}^s p_i^{e_i}, p_1\lt p_2\lt \cdots \lt p_s$ とおきます。
さらに各 $i=1, 2, \ldots, s$ について $t_1=1, t_i=\prod_{j=1}^{i-1} p_j^{e_j}$,
$p_i$ を法とする $r$ の位数を $o_i$,
$r^{o_i}-1$ を割り切る $p_i$ の指数を $f_i$
とおきます。
指数公式から $p_i$ が $r^n+1$ を割り切るとき $o_i=2l_i$ は偶数で $n$ は $l_i$ の倍数です。
$l_i\lt o_i\lt p_i$ より
$t_i=\prod_{j=1}^{i-1} p_j^{e_j}$ は $l_i$ の奇数倍です。
指数公式から $r^{t_i}+1$ を割り切る $p_i$ の指数 は $r^{l_i}+1$ を割り切る $p_i$ の指数と一致し、
それらは $f_i$ と一致します。
$n=t_i p_i^{e_i} \prod_{j=i+1}^s p_j^{e_j}$ より、指数公式から
$r^n+1$ を割り切る $p_i$ の指数は $e_i+f_i$ と一致します。
$n^k$ は $p_i^{ke_i}$ で割り切れますから
$r^n+1$ も $p_i^{ke_1}$ で割り切れる必要があります。
よって $ke_i\leq e_i+f_i$ つまり
$e_i(k-1)\leq f_i$ である必要があります。
これらのことから、
各 $i=1, 2, \ldots, s$ について
$o_i=2l_i$ が偶数で $l_i$ が $t_i$ の約数、なおかつ $e_i(k-1)\leq f_i$
となる必要があります。逆にこれらが成り立つとき
$r^n+1$ は各 $p_i^{ke_i}$ で割り切れるので $n^k$ で割り切れます。
したがって、次の判定法が得られます。
$r^n+1$ が $n^k$ で割り切れるための必要十分条件は $n$ が奇数で
各 $i$ について
- $o_i=2l_i$ が偶数で $l_i$ が $t_i$ の約数である
- $e_i(k-1)\leq f_i$
の両条件が成り立つことが必要十分である。
「マスターデーモン」の判定法の応用
ところで $r^n+1$ が $n^k$ で割り切れる $n$ が得られたとき、
$r^n+1$ の奇数の素因数で $n$ の素因数ではないものがあるとすると、それを一つとり、 $q$ とおき、
$r^n+1$ を割り切る $q$ の指数を $u$ とおきます。
$r^{nq^e}+1$ を割り切る $q$ の指数は $e+u$ と一致するので
$e(k-1)\leq u$ ならば $r^{nq^e}+1$ は $q^{ek}$ で割り切れます。
一方 $r^{nq^e}+1$ は $r^n+1$ の倍数ですから $n^k$ の倍数であることが明らかです。
よって $nq^e$ は新たな解を与えています。
ここで $u\geq k-1$ ならば、少なくとも $nq$ は新たな解を与えていることがわかります。
特に $k=1, 2$ のときは
$r^n+1$ の奇数の素因数で $n$ の素因数ではないもの $q$ があれば、そこから直ちに新たな解 $nq$ が得られます。
実は $(r, n)=(2, 3)$ のときと $(r, n)=(2^s-1, 1)$ のときを除いて
$r^n+1$ は必ず $n$ の素因数ではない奇数の素因数を持つことが知られています。
これは本質的には Bang (Taltheoretiske Undersøgelser, Tidsskrift Math. 5 IV (1886), 70--80, 130--137)
によって1886年に証明されましたが、
Shapiro, 上掲書、Theorem 6. 4A. 1 ではVandiver-Birkoffの定理として証明されています
（この一般化がZsigmondyの定理です）。
このことから
$r=2, 2^d-1$ でなければ $(r^n+1)/n^2$ が整数であるような整数 $n$ は無数に存在する
ことがわかります。また $r=2$ のとき $2^3+1$ は $3$ 以外の素数で割れないことから
$(r^n+1)/n^2$ が整数となるのは $n$ が $3$ の場合のみ（これが元の「マスターデーモン」の解となっています）、
$r=2^d-1$ のとき $r+1$ を割り切る素数が $2$ しかないことから $(r^n+1)/n^2$ が整数となる
$n\geq 2$ は存在しないことがわかります。