流れる空の中で数学を。

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

マスターデーモンの一般化、解の個数を調べてみた。

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

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

追記:証明に間違いがあるのに気づいたので、修正が必要です。

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

sky-time-math.hatenablog.jp

 

はじめに

前回の記事で、マスターデーモンを簡単に解く方法を紹介した。

sky-time-math.hatenablog.jp

ついでといってはなんだが、灘高の部誌(2008年度)で取り扱われていた一般化について少し考えてみたので書いておく。
なお、部誌の一般化のところはざっと目を通しただけでちゃんと読めてないので、細かいことを言われてもわかりません。(ごめんなさい。)

 

部誌に書いてあったマスターデーモンの一般化は次の通り。 

「一般の自然数rに対して、\frac{r^n+1}{n^2}\in \mathbb{Z}を満たす1より大きい自然数nを求めよ。」

というわけで、デーモンの2rになっている模様。 

 

また、同部誌では

「一般のrに対してこのようなnが無数に存在するか。」

が未解決問題として提示してあった。
ここでは、2番目の問題に答えてみる。
 

それでは、やってみる。

 

一般の自然数rの場合の解の個数

n=1の場合は自明なので、以下n \ge 2の場合のみ考える。

 

まず、r=2の場合にならって、r^n+1n^2で割り切れると仮定する。
仮定より、 r^n+1nが割り切れるので、

 r^n+1 \equiv 0 \pmod{n} \cdots

 
次に、前回の記事と同様に計算することで

 r^n+1
   \equiv (r-1)^n+1+1 \pmod{n}
   \equiv (r-2)^n+1+1+1 \pmod{n}
   \cdots
   \equiv r+1 \pmod{n} \cdots
となる。 
 

よって、①②式より、

  r+1\equiv 0  \pmod{n} \cdots

となり、なんだかかなり一般的式が得られるが、③式がnが満たすべき必要条件である。
そして、この式により、灘高の部誌で未解決とされていた二番目の問題が解決している!

 

すなわち、 n \gt r+1の場合を考えると、明らかに③式は成り立たたない。
よって、

 n \le r+1

となり、一般のrの場合のマスターデーモンの解は有限であることが言えた。

 

より詳細には、r+1素数p_1,p_2,\cdots, p_mを用いて、

r+1= p_1^{e_1} p_2^{e_2} \cdots p_{m}^{e_m}

素因数分解できた*1として調べればいい*2

 

このとき、③式から導かれるnの候補は、

 n=p_1^{k_1} p_2^{k_2} \cdots p_{m}^{k_m}

ここで、任意の組(k_1,k_2,\cdots,k_m)は、k_j=0,1,2,\cdots,e_jの値をとり得る。

 

従って、一般のrの場合のマスターデーモンの解の個数は、同じものを含む組み合わせの場合の数の問題を解けばわかります*3

 

特に、pを任意の素数として、r=p-1の場合は、③式を満たす2以上の自然数n n=p のみである。
一般解についても調べてみようかと思ったけど、かなり大変そうなので少し疲れてきたので、ひとまずここまでということで。

*1:mは適当な0以上の整数

*2:e_1,e_2,\cdots, e_mは適当な0以上の整数。

*3:少し面倒なので、今はやりません。