$n^k$ が $r^n+1$ を割り切る $n$ について

2019年8月30日作成

「マスターデーモン」とその一般化

1990年の数学オリンピックに出題された次の問題は「マスターデーモン」として広く知られています。

整数 $n\geq 2$ で、$\frac{2^n+1}{n^2}$ が整数となるものをすべて求めよ。

先日twitterでFoxQ氏がこの変形とも言える問題を出題し、先日の数学デーでもこの問題が話題となりました。

[FoxQからの出題]
19の倍数でない自然数n≧2に対して、
(8^n+1)/n^3
が自然数となるようなnを全て求めよ。 pic.twitter.com/vE4V8hLbQd

— FoxQ@固定ツイにて出題中第2回(前回より簡単) (@foxq_stm) August 25, 2019

これについては、$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$

の両条件が成り立つことが必要十分である。

特に $l_1=1$ で $p_1$ は $r+1$ の約数である必要があります。

---

「マスターデーモン」の判定法の応用

ところで $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 Undersogelser, 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$ は存在しないことがわかります。