3

マスターデーモン

2519
0
$$$$

以前、生徒から出題された問題を紹介します。

マスターデーモン

$\displaystyle\frac{2^n+1}{n^2}$が整数になるような正の整数$n$を求めよ.

生徒から出題されたオリジナルの問題では、分母が$n$でした。
この場合も解けないことはないのですが、かなり面倒になるので、マスターデーモンとして有名な$n^2$にしてみました。
$\displaystyle\frac{2^n+1}{n^2}$が整数なら、$\displaystyle\frac{2^n+1}{n}$も整数となります。

$\displaystyle\frac{2^n+1}{n}$が整数ならば、$\displaystyle\frac{2^{3n}+1}{3n}$も整数である。

$2^n+1$は常に奇数なので,仮定を満たすような$n$は偶数ではない.
$$\frac{2^{3n}+1}{3n}=\frac{(2^n+1)(4^n-2^n+1)}{3n}=\frac{2^n+1}{n}\times \frac{4^n-2^n+1}{3}$$
$n$が奇数のとき,$4^n-2^n+1 \equiv 0 (\mod 3)$より
$$\frac{2^{3n}+1}{3n}$$
も整数である.

$\displaystyle\frac{2^n+1}{n}$が整数ならば、$n=1$または$n$$3$の倍数である。

$2^n+1 \equiv 0(\mod n)$とする.
$n$$3$以上の奇数とする.
$n$の素因数のうち最小の素数を$p$として$n=pm$とおく.
$2^{pm}+1 \equiv 0(\mod p)$
Fermatの小定理より,$2^{mp} \equiv 2^m(\mod p)$
よって
$2^m \equiv -1(\mod p)$
$2^{2m} \equiv 1(\mod p)$
$\mod p$での$2$の位数を$k$とする.
すなわち$k$$2^k \equiv 1(\mod p)$を満たす最小の正の整数とする.
$k$$2m$および$p-1$の約数である.
$k$が奇数と仮定すると,$m$は奇数なので,$k$$m$の約数である.すると,
$2^m \equiv (2^k)^\frac{m}{k} \equiv 1(\mod p)$となり矛盾する.
よって$k$は偶数であり,$k=2d$とおくと$d$$m$の約数である.
$k$$p-1$の約数なので$p$より小さく,$d=\frac{k}{2}$もまた$p$より小さい.
$n$の素因数のうち最小の素数を$p$として$n=pm$とおいたので,$m$の素因数は$p$以上である.
したがって$d=1$となるので,$2^2 \equiv 1(\mod p)$より$p=3$

$p$を奇素数とする.
$\displaystyle\frac{2^{3p}+1}{3 p}$が整数ならば、$p=3$である。

$$\frac{2^{3p}+1}{3p}=\frac{(2^p+1)(4^p-2^p+1)}{3p}$$
奇素数$p$について,Fermatの小定理により,$4^p \equiv 4(\mod p)$,$2^p \equiv 2(\mod p)$より,$4^p-2^p+1\equiv 3(\mod p)$である.
$p$$4^p-2^p+1$の素因数ならば,$p=3$である.
$p$$2^p+1$の素因数ならば,$p=3$である.

$p$を奇素数とする.
$\displaystyle\frac{2^{9p}+1}{9p}$が整数ならば、$p=3,19$である。

$$\frac{2^{9p}+1}{9p}=\frac{(2^p+1)(4^p-2^p+1)(4^{3p}-2^{3p}+1)}{9p}$$
Fermatの小定理より,$4^{3p}-2^{3p}+1 \equiv 64-8+1=57(\mod p)$
$p=3,19$

$\displaystyle\frac{2^n+1}{n}$が整数ならば,$n$の素因数は$2^{3^k}+1$の素因数である.

$\displaystyle\frac{2^n+1}{n^2}$が整数になるような正の整数は $n=1,3$の場合のみである。

証明は楽ではありませんが、挑戦してみると面白いと思います。出題してくれた生徒は「LTEの補題」を使って解いたそうです。私は知りませんでしたが、数学オリンピックでは定石の手法らしいです。
次に、私から生徒に向けて出題した問題を紹介します。

$a^n-1=p^m$を満たす$2$以上の正の整数$a,n,m,p$(ただし$p$は素数)を求めよ。

私はこの問題を解くのに相当な労力と時間を費やしましたが、本校の生徒は数日で解答を作ってきました。この問題のもとになっているのは「カタラン予想」です。

カタラン予想

$x^a-y^b=1$を満たす$2$以上の整数$x,y,a,b$は、$3^2-2^3=1$のみである。

現在は証明されて定理となっています。
以下の補題は、通称「LTEの補題」と呼ばれています。

Lifting The Exponent Lemma

整数$a$$p$でちょうど$n$回割れるとき,$n=(a{)}_p$と表す.
$p$を奇素数,$x-y$$p$の倍数かつ$x,y$$p$の倍数ではないとき,
$(x^n-y^n{)}_p=(x-y{)}_p+(n{)}_p$ が成り立つ.

 この補題を使って問題2を解いてみましょう。

まず、$p$が奇素数の場合を考える。
$a$$3$以上のとき、$(a^n-1{)}_p=(a-1{)}_p+(n{)}_p$より、$(n{)}_p$は正の値をとる。
$A=a^{\frac{n}{p}}$とおくと、$A^p-1=p^m$となるので、$(A^p-1{)}_p=(A-1{)}_p+(p{)}_p$より、$A-1=p^{m-1}$となる。よって、$A^{p-1}+\cdots+A+1=p$となるが、これは矛盾である。なぜなら、$A$$3$以上なので左辺は$p$を超える。
$a=2$のとき、$p^m-1=2^n-2$となるので、$m$は奇数である。
なぜなら、$m$が偶数だと、$p^m-1=(p-1)(p^{m-1}+\cdots+1)$と因数分解すると、$2^n-2$$4$の倍数ということになり矛盾が生じる。
$m$が奇数なら、$p^m+1=(p+1)(p^{m-1}+\cdots+1)$と因数分解できる。
$\displaystyle{\frac{p^m+1}{p+1}}$は奇数となるので、$p^m+1=2^n$が成り立つためには、$m=1$でなければならない。$m$$2$以上としているので、この場合は解がない。
 次に$p=2$とする。$a^n-1=2^m$より$a$は奇数である。
$\displaystyle{\frac{a^n-1}{a-1}}$が偶数となるので、$n$は偶数でなければならない。
$a^{\frac{n}{2}}=b$とおくと、$b^2-1=2^m$となる。
このような式が成立するのは、$3^2-1=2^3$のみである。

投稿日:202117
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

DIO
DIO
18
4358

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中