Størmerの定理

前書き

$2^{n} - 3^{k} = 1$ を満たす正の整数 $(n,k)$ をすべて求めなさい。

いきなりですが、上記の問題が解けるでしょうか？

まず小さい数を代入していくと、$(n,k) = (2,1)$ の時は $2^{2} - 3^{1} = 1$ となってこれを満たすことがわかります。それ以外の解は見つかるでしょうか？何となく無さそうですが確証は持てないですね…

こういう問題は指数型の不定方程式とか呼ばれているそうです。受験で出てきそうな見た目をしていますが、この問題は凶悪なのか解法は見たことがないです。この問題、解きたいですよね？

今回は Størmerの定理(Stormerの定理) と呼ばれている定理を用いて、$2^{n} - 3^{k} = 1$ を満たす正の整数 $(n,k)$ は $(n,k) = (2,1)$ のみであることを証明します。

今回の証明は http://kam.mff.cuni.cz/~klazar/stormer.pdf を要約したものとなっています。

有限集合 $P = \{p_{1},p_{2}, \cdots, p_{k}\}$ を一つ選び、$P$-smooth 数を以下のように定義する。

$$ Ps = \{p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k} | e_{i} \in \{0,1,2, …\} \} $$

この時、 $x - y = 1,2 | x,y \in Ps$ を満たす $(x,y)$ の組は最大でも $3^{k}$ 個しかなく、更に全ての解はペル方程式を用いて求めることが出来る。

例えば $P = \{2,3\}$ の時、 $P$-smooth 数は、

$$ 2,3,4,6,8,9,12,16,18,24,27,32,36,48, \cdots $$ となります。

また、$x$-smooth (xは正の整数) を、xの素因数の集合 $PF(x) = \{p_{1},p_{2}, \cdots, p_{k}\}$ を使って、$Px$-smooth と同様なものと定義します。

例えば$20$-smoothな数は$\{2,5\}$-smooth 数と同等です。

なお、$PF(1) = \phi$は面倒なので考えません、あしからず。

ペル方程式

$$ x^{2} - Dy^{2} = 1 | x,y,D \in \{1,2,3, \cdots \} $$ という形をしたものをペル方程式 といいます。 $= \pm 1$ だったり $= \pm n$ だったりするんですが、今回は $= 1$ でいきましょう。

ここで、$D$ が平方数の時は簡単で、 $(x-\sqrt{D} y) (x+\sqrt{D} y) = 1$ を解けば良いです。

一方で $D$ 平方数でないときは以下の性質があります

解が無限にある
解を$x,y$それぞれについて小さい順に並べた時、以下の漸化式が成り立つ

$$ x_{k} + y_{k} \sqrt{D} = (x_{1} + y_{1} \sqrt{D})^{k} $$

$x_1,y_1$ を 基本解 と呼ぶ。

ペル方程式の基本解の求め方はここでは述べませんが、詳しく知りたい方は以下の本がお勧めです。

はじめての数論原著第3版発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

作者: Joseph H. Silverman,鈴木治郎
出版社/メーカー: 丸善出版
発売日: 2014/05/13
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

以下では、ペル方程式の基本解はなんらかの手続きによって求められることを保証するものとします。

$P = \{2,3\}$ の時

具体例に戻りましょう。

$P = \{2,3\}$ の時、連続する数 $P$-smooth 数は以下の不思議な解法で求められます。現時点では意味不明な手続きですが、流れはくみ取れるかと思います。

ペル方程式について、$D \in \{1,2,3,4,6,9,12,18,36\}$ の基本解のみ考えればよい。ただし Dが平方数の時は除く。それぞれの基本解は,

$D = 2$ の時 $(x,y) = (3,2)$
$D = 3$ の時 $(x,y) = (2,1)$
$D = 6$ の時 $(x,y) = (5,2)$
$D = 12$ の時 $(x,y) = (7,2)$
$D = 18$ の時 $(x,y) = (17,4)$

となる。この結果から、 $x^2 - 1$ が $P$-smooth になるような$x$は$x = 2,3,5,7,17$ のみであることが分かる。

$a, a+1$が共に $P$-smooth の時 $4a(a+1) = (2a+1)^2 - 1$ より、奇数解 $x = 3,5,7,17$ について、 $(a,a+1) = (1,2), (2, 3),(3,4), (8,9)$ が差が$1$の$P$-smooth な数である。

同様に、$a, a+2$が共に$P$-smooth の時 $a(a+2) = (a+1)^2 - 1$より、全ての解 $x = 2,3,5,7,17$について、 $(a,a+2) = (1,3), (2, 4),(4,6), (6,8), (16,18)$ が差が$2$の$P$-smooth な数である。

またこの結果から、$2^{n} - 3^{k} = 1$ を満たす正の整数 $(n,k)$ は、 $(n,k) = (2,1)$ のみであることが分かった。

Størmerの定理の証明

この定理と、解を求める手続きの肝は、

ペル方程式について、$D \in \{1,2,3,4,6,9,12,18,36\}$ の基本解のみ考えればよい。ただし Dが平方数の時は除く。

…

この結果から、 $x^2 - 1$ が $P$-smooth になるような$x$は$x = 2,3,5,7,17$ のみであることが分かる。

の2箇所です。

Størmerの定理を追いながら、何故このようなことが言えるのか考えていきます。

証明の流れを大まかに紹介すると、

$P = \{p_{1},p_{2}, \cdots, p_{k}\}$ ($p_{k}$ は素数) なる $P$ について、$P$-smoothな数を $Ps$と定義する。

(1) $a^2-1 \in Ps$ なる $a$ を求めれば、$x - y = 1, 2 | x,y \in Ps$ となる $(x,y)$ を求める事が出来る

(2) ところで $ x^{2} - dy^{2} = 1 | x,y,d \in \{1,2,3, \cdots \} $ について、$x^{2}-1$ が $d$-smooth になるような $y$ は、基本解以外にない。

(3) $a^2-1 = Db^2$ と分解できる。そこで、 $a^2-1 = \prod p_{k}^{a_{k}} $ の時 $D = \prod p_{k}^{d_{k}}$ とする。ただし、$d_{k}$は以下のように定める。 $$ d_{k} = \begin{cases} 0 (a_{k} = 0) \\ 1 (a_{k} \% 2 = 1) \\ 2 (a_{k} > 0, a_{k} \% 2 = 0) \end{cases} $$ の3種類の値とする。

$d_{k} \in \{0, 1\} $ にしない理由は後で明らかになります。なお、各k について $d_{k}$の値は3通りなので、このような$D$は$3^{|P|}$ 個しかありません。

$$Ds = \{ \prod_{p_{k} \in P} p_{k}^{d_{k}} | d_{k} \in \{0,1,2\} \}$$

と定義しておきましょう。先述の通り、$|Ds| = 3^{|P|}$ となります。

(4) よって、全ての $D \in Ds$ について、 $ x^{2} - Dy^{2} = 1 | x,y \in \{1,2,3, \cdots \} , D \in Ds $ の基本解を求めることで、全ての $P$-smooth な $x^2-1$ を求めることが出来る。

順に証明していきましょう。

(1)

$a^2-1 \in Ps$ なる $a$ を求めれば、$x - y = 1, 2 | x,y \in Ps$ となる $(x,y)$ を求める事が出来る

まず、$x - y = 1 | x,y \in Ps$　について、これを満たすためにはどちらか一方が偶数である必要があります。よって、$2 \in Ps$ の時だけ考えれば十分です。そうでなければ、そのような$(x,y)$は存在しません。

$a, a+1$が共に $P$-smooth の時 $4a(a+1) = (2a+1)^2 - 1$ であり、$(2a+1)^2 - 1$は$P-smooth$ です。よって、逆に $x^2-1$が$P$-smoothならば、$x$が奇数の時に限り、式を解くことで$a, a+1$を求めることが出来ます。

同様に、$x - y = 2 | x,y\ \in Ps$　について、$a, a+2$が共に$P$-smooth の時 $a(a+2) = (a+1)^2 - 1$ であり、$(a+1)^2 - 1$は$P-smooth$ です。よって、逆に $x^2-1$が$P$-smoothならば $x-y = 1$の時と同様に、式を解くことで$a, a+2$を求めることが出来ます。

(2)

$ x^{2} - Dy^{2} = 1 | x,y,D \in \{1,2,3, \cdots \} $ について、$x^{2}-1$ が $D$-smooth になるような$y$は、基本解以外にない。

例えば $D = 18$ の時、$18$-smooth = $\{2,3\}$-smooth となるような$y$について考えましょう。この解は小さい順に、 $$(x,y) \in \{(17, 4), (577, 136), (19601, 4620), (665857, 156944), (22619537, 5331476), \cdots \}$$ です。実際に因数分解してみると、$4 = 2^2, 136 = 2^3 * 17, 4620 = 2^2 * 3 * 5 * 7 * 11, 156944 = 2^4 * 17 * 577, 5331476 = 2^2 * 19 :29 *41 * 59$ となります。

よってこの中で$18$-smoothな$y$は確かに基本解$(x,y) = (17,4)$ の$y_1 = 4$ を除いて無さそうな雰囲気はあります、が確証は持てませんね…

これを実際に証明してみましょう。

背理法で示します。

$ x_{k} + y_{k} \sqrt{D} = (x_{1} + y_{1} \sqrt{D})^{k} $　が成り立つことは前に紹介しました。このことから $$ \begin{eqnarray} x_{kl} + y_{kl} \sqrt{D} &=& (x_{1} + y_{1} \sqrt{D})^{kl} \\ &=& ((x_{1} + y_{1} \sqrt{D})^{k})^{l} \\ &=& (x_{k} + y_{k})^{l} \end{eqnarray} $$

が成り立つこともわかります。また、右辺を展開して二項係数を使うと、 $$ y_{kl} = \binom{l}{1} x_{k}^{l - 1}y_{k} + \binom{l}{3} x_{k}^{l-3}y_{k}^{3} D + \cdots $$ が成り立つことがわかりました。つまり $y_{kl}$ は $y_{k}$ の倍数です。このことから、$y_{k}$が $D$-number でなければ、その倍数である $y_{kl}$ も $D$-number ではないので、あらゆる素数$p$ について、$y_{p}$ が $D$-number ではないことが証明できれば十分であることがわかりました。

では実際に$y_{p}$ について考えます。 $(k,l) = (1,p)$を代入して $$y_{p} = y_{1} (\binom{p}{1} x_{1}^{p-1} + \binom{p}{3} x_{1}^{p-3}y_{1}^{2} D + \cdots ) $$ が成り立ちます。 $y_{p}$ が $D$-numberであるためには $y_{1}$ と $\binom{p}{1} x_{1}^{p-1} + \binom{p}{3} x_{1}^{p-3}y_{1}^{2} D + \cdots$ の両方が $D$-number である必要があることがわかります。後者について、 $$ 　　c_{p} = \binom{p}{1} x_{1}^{p-1} + \binom{p}{3} x_{1}^{p-3}y_{1}^{2} D + \cdots = p x_{1}^{p-1} + D(\binom{p}{3} x_{1}^{p-3}y_{1}^{2} + \cdot) $$ と置きます。 $c_{p}$が$D$-number であると仮定すると、 $c_{p}$ が素数 $q$ の倍数であるとき $q$は$D$-number であり、$p x_{1}{p-1}$ を割りきることが分かります。

ところが $x_{1}$は $D$ と互いに素であることから (互いに素でなければ $x^{2} - dy^{2} = 1$ は満たせないため) $p = q$以外にないことが分かりました。つまり、$c_{p}$ の素因数は $p$ のみです。また$p \ge 2$であることから明らかに $c_{p} = p^r (r \ge 1)$ を満たします。

$p \ge 5$ の時、$c_{p}$の第2項以降は明らかに$p^2$で割り切れるので、第一項も$p^2$で割り切れる必要がありますが、$x_{1}$は$p$と互いに素なので、これに矛盾します。なので$p = 2,3$ の時を具体的に考えれば十分です。

次に$p = 2$の時、$c_{2} = 2x_{1}$ なので、明らかに $c_{2}$ は $D$-number ではありません。

最後に$p = 3$の時、$c_{3} = 3x_{1}^{2} + y_{1}^{2}D = 4x_{1}^{2} - 1 = (2x_{1} - 1)(2x_{1} + 1)$ が成り立ちます。 $2x_{1} - 1, 2x_{1} + 1$ の両方が $3^k$の形になるような $x_{1}$は $1$しかありませんが、$x_{1} > 1$であることから矛盾します。

以上のことから、全ての$p$ について $y_{p}$が$D$-numberでないことがわかりました。よって、$y_{k}$が$D$-numberとなり得る$k$ は$k = 1$しかありません。

(3)

$a^2-1 = db^2$ と分解できる。そこで、 $a^2-1 = \prod p_{k}^{a_{k}} $ の時 $D = \prod p_{k}^{d_{k}}$ とする。ただし、$d_{k}$は以下のように定める。 $$ d_{k} = \begin{cases} 0 (a_{k} = 0) \\ 1 (a_{k} \% 2 = 1) \\ 2 (a_{k} > 0, a_{k} \% 2 = 0) \end{cases}$$ の3種類の値とする。

天下り的な定義が出てきました。何故このような$d$の選び方をするのか考えていきます。

$a_{k} = 0,1,2,3,4,5,6, … $の時、それぞれ $d_{k}$は$d_{k} = 0,1,2,1,2,1,2, …$ と変化していきますが、 $d_{k} = 0,1,0,1,0,1,0, …$ ではだめなのでしょうか？こちらて定義の方が自然な気がしますが。

ここで、ある $x^2-1 \in Ps$, つまり $x^2-1$が$P$-smooth な数の時を考えます。

$x^2-1$の素因数の集合$PF(x^2-1)$ は明らかに$PF(x^2-1) \subset P$を満たしますが、 $PF(x^2-1) = P$ とは限りません。そこで$Q = PF(x^2-1)$ と定義します。

ところで$D$の定義から、$PF(D) = Q$ が明らかに満たされます！何故なら $a_{k} > 0$ ならば、必ず $d_{k} > 0$を満たすからです。これの何が嬉しいかというと、先の定理により、 $PF(D) = Q$ の時 $Q$-smooth な $dy^2 = x^2-1$ が最大でも1つだけ存在するということが言えるからです。

このことから全ての $D \in Ds$ について、 $ x^{2} - Dy^{2} = 1 | x,y \{1,2,3, \cdots \} , D \in Ds $ の基本解を求めることで、全ての $P$-smooth な $x^2-1$ を求めることが出来ます。

(4)

よって、全ての $D \in Ds$ について、 $ x^{2} - Dy^{2} = 1 | x,y \{1,2,3, \cdots \} , D \in Ds $ の基本解を求めることで、全ての $P$-smooth な $x^2-1$ を求めることが出来る。

結論です。お疲れ様でした。

後書き

証明の (2) が結構なボリュームになりましたがいかがでしょうか。

これで $2^{n} - 3^{k} = 1$ が解けますね、おめでとうございます。

他にも証明する方法があったら教えてください。 $2^{n} - 3^{k} = 1$ に限ればもっと簡単な方法がある！なども大歓迎です。

追記:

$2^{n} - 3^{k} = 1$ はもっと簡単に求められるようで、twitterでも問題として出題されていました。

2^n-3^m＝±1が成立するような自然数n,mの組を全て求めよ。（tokoharu_sakura様） #数学
— 数学問題bot (@mathematics_bot) 2016年12月23日