マスターデーモン
以前、生徒から出題された問題を紹介します。
$\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の補題」と呼ばれています。
整数$a$が$p$でちょうど$n$回割れるとき,$n=(a{)}_p$と表す.
$p$を奇素数,$x-y$は$p$の倍数かつ$x,y$は$p$の倍数ではないとき,
$(x^n-y^n{)}_p=(x-y{)}_p+(n{)}_p$ が成り立つ.
この補題を使って問題２を解いてみましょう。
まず、$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$のみである。