整数問題

466

はじめに

どうもぷりんねこです。整数論や数学のいろいろなことについて書いていこうと思います。数学の記事を書くのは初めてなので拙いものかもしれませんが読んでいただければ幸いです。

整数論

ここでは理論の解説はせずに、どうやって問題を解いていくのかなどの思考プロセスの部分を書いていこうと思います。理論を学びたいのであれば、「マスターオブ整数」（東京出版）または、難しいですが「初等整数論講義」（高木貞治）がいいと思います。
数学の本などを読んでいると、どうやって思いつけば良いのかわからないような解説などが結構あります（僕自身もよく出会います）。そのようなものに苦しんでいる方々の助けに少しでもなれたらいいかなーと思います。なるべく丁寧に書いていくつもりなので分かるとこはどんどん飛ばしてもらって大丈夫です！
問題の難易度は筆者の主観によって☆１から☆５までに分類されます。
では早速いきましょう！（問題はまず自分で解いてみることをおすすめします）

☆1

(1) $3^{n} = k^{3} + 1$ を満たす正の整数の組 $(k, n)$ を全て求めよ。
(2) $3^{n} = k^{2} - 40$ を満たす正の整数の組 $(k, n)$ を全て求めよ。
（2010　千葉大-医）

思考過程

よく知られていますが、整数問題には解くときに意識するといい３つの鉄則のようなものがあります。

鉄則

（素）因数分解して積の形にする
不等式で文字の範囲を絞り込む
約数,倍数,余り(mod)に注目する

この３つをしっかり使えるようになるだけで整数問題が一気に解けるようになると思います。

この問題は鉄則の1を使うことができますね。右辺が因数分解できることに気づけたのでラッキーです。因数分解すると、

$3^{n} = (k + 1) (k^{2} - k + 1)$

となります。ここで、左辺が $3$ （素数）の冪乗なので、 $k + 1, k^{2} - k + 1$ も $3$ の冪乗になるはずです。それぞれ文字でおいてあげましょう。

$k + 1 = 3^{p}$
$k^{2} - k + 1 = 3^{q}$

とします。( $p, q$ は1以上の整数。 $p, q$ がそれぞれ $0$ のときに成り立たないことはすぐわかります）
一つ目の式から $k$ を消去します。 $k = 3^{p} - 1$ を二つ目の式に代入して、整理すると

$3^{p} (3^{p - 1} - 1) + 1 = 3^{q - 1}$

となります。ここで、 $3^{p} (3^{p - 1} - 1)$ の部分が $3$ の倍数なので右辺も $3$ の倍数なら、 $1$ が $3$ の倍数じゃないので矛盾します。よって $3^{q - 1} = 1$ となり、 $q = 1$ が必要です。 $k^{2} - k + 1 = 3^{q}$ に代入して、 $k = 2$ が必要です。 $3^{n} = k^{3} + 1$ に $k = 2$ を入れてみると、 $n = 2$ となりうまくいきます（十分）。
よって $(k, n) = (2, 2)$ のみ。

（感想）
見た目は難しそうでしたがけっこう一直線に終わりました。素数の冪乗を積の形にしてそれぞれ文字でおくやり方はしばしば使います。

(2)このままでは何も情報がないのでとりあえずmodを回しにいきます。
$3^{n}$ が消えてほしいので $\mod 3$ でみると、与式は
$k^{2} \equiv 1 (\mod 3)$ となります。

$k \mod 3$	0	1	2
$k^{2} \mod 3$	0	1	1

よって上の表から $k \equiv 1, 2 (\mod 3)$ となります。
ここからちょっと考えましたがあまり議論は進みませんでした。
では次は $40$ を消すために $\mod 4$ をみてみると、与式は
$(- 1)^{n} \equiv k^{2} (\mod 4)$
となります。さっきと同じ感じで表をかくと

$k \mod 4$	0	1	2	3
$k^{2} \mod 4$	0	1	0	1

となります。表から $k^{2}$ は $0$ か $1$ のどちらかです。また、 $(- 1)^{n}$ は $n$ が偶数のとき $1$ と等しく、 $n$ が奇数のとき $- 1$ と等しいので
$k^{2} \equiv (- 1)^{n} \equiv 1 (\mod 4)$ となる必要があり、 $k$ は奇数で、 $n$ は偶数です。 $n = 2 m$ とおいて与式に代入すると
$3^{2 m} = k^{2} - 40$ となり、これは「 $a^{2} - b^{2}$ 」の形の因数分解が使えます！
$(k - 3^{m}) (k + 3^{m}) = 40$ となるので $k - 3^{m} = M, k + 3^{m} = N$ などとおいてやると結局
$M < N$
$M N = 40$
$N - M = 2 \cdot 3^{m}$
を解けばいいとわかります（ $k$ は自動的に決まる）
一つ目と二つ目の式から $M, N$ の候補は以下のようになります

M	1	2	4	5
N	40	20	10	8

このうち $M, N$ の差が $2 \cdot$ ( $3$ の冪乗)となるようなものを探すと
$(M, N) = (2, 20), (4, 10)$
でありこれらのとき $(k, n) = (11, 4), (7, 2)$ となり与式をみたすので、解はこれらのみです。

（感想）
こちらはmodをみて因数分解するだけでした。 $\mod 3, 4$ で平方数が $0, 1$ に等しくなるのはめっちゃ重要です！！　（一つ目と二つ目の表からわかります）

記号、用語について

(i) $a$ が $b$ を割り切るとき、 $a ∣ b$ と表します。
例： $7 ∣ 21$
(ii) $p$ を素数とします。このとき $n \in Z$ に対して、 $n$ が $p$ で割り切れる回数、すなわち $n$ を素因数分解したときの $p$ の指数を $v_{p} (n)$ で表します。便宜的に、 $v_{p} (0) = \infty$ とします。
例： $v_{2} (8) = 3, v_{3} (7) = 0, v_{5} (- 15) = 1$
(iii) $a$ と $b$ の最大公約数を $g c d (a, b)$ で表します。
例： $g c d (12, 42) = 6$
(iv)素数のべき乗の形であるような数のことを単に素べきといいます。
例： $81 = 3^{4}$ より $81$ は素べきです

☆2

$8^{n} + n$ が $2^{n} + n$ の倍数となるような正の整数 $n$ を全て求めよ。
(JMO/2009　本選1)

思考過程

こういう問題は、割り算の形にしてそれが整数となることを示すやり方が多いのでそれを使ってみます。つまり、 $k = \frac{8^{n} + n}{2^{n} + n} \in Z$ であるような $n$ を探すことにします。
分母、分子のどちらにもある $+ n$ の部分がじゃまなので $2^{n} + n$ をくくり出して $+ n$ を消すことを考えます。整理すると、
$k = \frac{2^{n} (2^{n} - 1) (2^{n} + 1)}{2^{n} + n} + 1 \in Z$
となるので、 $\frac{2^{n} (2^{n} - 1) (2^{n} + 1)}{2^{n} + n} \in Z$
が必要十分条件です。ここで、 $n$ が奇数なら $2^{n} + n$ も奇数となり、 $2^{n}$ と互いに素になるので $\frac{(2^{n} - 1) (2^{n} + 1)}{2^{n} + n} \in Z$ が得られ、議論が進みそうなので偶奇を調べます。 $\mod 2$ をみてみましたが何も起こらず行き詰まります。悩んでいても仕方ないので $n = 2 m$ とおいて、まず $n$ が偶数の時を調べました。与式に代入して、
$2^{2 m} + 2 m ∣ 8^{2 m} + 2 m$ 両辺2で割って、 $2^{2 m - 1} + m ∣ 2^{6 m - 1} + m$ となります。同様に、" $+ m$ "の部分が消えるように差をとって、 $2^{2 m - 1} + m ∣ 2^{6 m - 1} + m - (2^{2 m - 1} + m) = 2^{2 m - 1} (2^{4 m} - 1)$ となりますが、これも最初と似た形になり、進捗が生まれません。なので、議論をさかのぼって $g c d (2^{n} + n, 2^{n})$ を考えてみました。
ユークリッドの互除法からこれは $g c d (2^{n}, n)$ に等しく、 $2^{n}$ が素ベきであることに注目すると、 $n$ が何回2で割り切れるかが気になってきます。
$v_{2} (n) = l$ とすると、
$n = 2^{l} \cdot t$ （ $t$ は奇数）とできます。 $l \geq 2$ のとき、二項定理より、
$n = 2^{l} \cdot t \geq 2^{l} = (1 + 1)^{l} = 1 +_{l} C_{1} + \dots + 1 \geq l + 2 > l$ なので、 $n > l$ であり、この不等式は $l = 0, 1$ のときも成り立つので、一般に $n > l$ が成立します。よって $g c d (2^{n}, n) = 2^{l}$ 、すなわち $g c d (2^{n} + n, 2^{n}) = 2^{l}$ が得られました。 $n = 2^{l} \cdot t$ を $\frac{2^{n} (2^{n} - 1) (2^{n} + 1)}{2^{n} + n}$ に代入して、 $g c d (2^{n}, n) = 2^{l}$ を使って約分して、と思いましたが流石に複雑すぎると思ったのでこのやり方もやめておきましょう。でも、色々試行錯誤しているうちに、脳が働いてきて、問題の本質が見えやすくなってきました。実験することは非常に大切です。さて本題に戻りましょう。 $\frac{2^{n} (2^{n} - 1) (2^{n} + 1)}{2^{n} + n}$ の式の形から、Zsigmondyの定理とか、LTEの補題とかが浮かびますが後で試すことにしましょう。一応↑の2つがどんなものであるか書いときます。どちらも美しい定理なのでいつかまた別の記事で解説すると思います。今は紹介だけにとどめておきます

Zsigmondyの定理

$a, b$ を互いに素な正の整数、 $n$ を $2$ 以上の整数とする。このとき、 $2^{6} - 1^{6}$ および $n = 2$ かつ $a + b$ が $2$ の冪であるという例外ケースを除いて、 $a^{n} - b^{n}$ のある素因数 $p$ が存在して、 $p$ は $1 \leq k \leq n - 1$ なる任意の整数 $k$ に対して $a^{k} - b^{k}$ を割り切らない

LTEの補題

$p$ が奇素数, $x, y$ が $p$ で割り切れない整数で $x \equiv y (\mod p)$ なら,
$v_{p} (x^{n} - y^{n}) = v_{p} (x - y) + v_{p} (n)$
が成り立つ.

さて、ここまで色々やってきましたが何もうまく行きませんね。最初から考え直してみましょう。最初は" $+ n$ "の部分を消しましたが、 $8^{n}$ の部分を消してみてはどうでしょう。3乗の和の因数分解公式を使って $8^{n}$ を $2^{n} + n$ で消しにいきましょう。 $2^{n} + n ∣ (2^{n})^{3} + n^{3} = 8^{n} + n^{3}$ なので、
$2^{n} + n ∣ 8^{n} + n ⟺ 2^{n} + n ∣ 8^{n} + n^{3} - (8^{n} + n) = n^{3} - n$
つまり $2^{n} + n ∣ n^{3} - n$ が必要十分条件です。
ここで $n > 1$ のときを考えます。 $2^{n} + n > 0$ , $n^{3} - n > 0$ なので、 $n^{3} - n \geq 2^{n} + n$ が必要です。しかし、直感的にも分かるとおり $n$ が十分大きいとき $2^{n} + n > n^{3} - n$ となって矛盾します。ここから $n$ の範囲（上界）がわかります。（←これは鉄則の2です！）あとは簡単ですね。表などを書いて調べてみましょう。題意を満たすものには◯をつけました

$n$	$2^{n} + n$	$n^{3} - n$
2	6	6	◯
3	11	24	×
4	20	60	◯
5	37	120	×
6	70	210	◯
7	135	336	×
8	264	504	×
9	521	720	×
10	1034	990	×
11	2059	1320	×

表から、 $n \geq 10$ なら $2^{n} + n > n^{3} - n$ となりそうですね。これをちゃんと証明しましょう。やり方は色々考えられますが（微分、二項展開、グラフの差がどんどん大きくなっていくことを示す、など）ここでは素直に帰納法を使って示してみます。

$n \geq 10$ ならば $2^{n} - n^{3} + 2 n > 0$

$n = 10$ のとき明らかに成立する。
$n = k (k \geq 10)$ のときに成立すると仮定する。
$n = k + 1$ のとき、
$2^{k + 1} - (k + 1)^{3} + 2 (k + 1) = 2 (2^{k} - k^{3} + 2 k) + k^{3} - 3 k^{2} - 5 k + 1$
仮定から $2^{k} - k^{3} + 2 k > 0$ で、簡単な計算により $k \geq 10$ のとき $k^{3} - 3 k^{2} - 5 k + 1 > 0$ であることもわかるので、この場合も成立する。
よって数学的帰納法から、示された。

この補題から、 $n < 10$ の範囲で調べれば十分であり、上の表から
$n = 2, 4, 6$ のみであるとわかる。
また、 $n = 1$ も題意を満たすので、以上を合わせて、
$n = 1, 2, 4, 6$ が解。

（感想）いったん解けてしまうとあっけないですね。最初らへんでめちゃくちゃ無駄な考察いっぱいしてますね、、結局Zsigmondyの定理とLTEの補題も使いませんでしたしw　無駄に知識が多いと僕のように沼ったりします。今回のポイントは
（指数関数）>> （多項式）という直感的な不等式です。ここら辺の感覚は練習すれば身についてきます。余談ですが、 $2^{n} + n > n^{3} - n$ よりも強い $2^{n} > n^{3}$ を示すこともできます。こちらは簡潔に証明できます。
$f (n) = \frac{n^{3}}{2^{n}}$ とすれば $n \geq 10$ のとき
$\frac{f (n + 1)}{f (n)} = \frac{1}{2} \cdot (1 + \frac{1}{n})^{3} \leq \frac{1}{2} \cdot (1 + \frac{1}{10})^{3} < 1$ なので $f (n)$ は単調減少な関数で、任意の $n$ に対して $f (n) \leq f (10) = \frac{125}{128} < 1$ となり、証明が完了します。

☆１

$n$ が相異なる素数 $p, q$ の積 $n = p q$ であるとき $n - 1$ 個の数 $_{n} C_{k} (1 \leq k \leq n - 1)$ の最大公約数は $1$ であることを示せ
（京大ー理系）

思考過程

さて、二項係数の最大公約数についての問題ですね。最大公約数を直接求めに行くのはさすがに厳しそうなので、最大公約数が $1$ にしかなりえないことを示しましょう。また、 $n$ が相異なる素数の積という特殊な形をしていることも使えそうです。まずわかることとして、 $_{n} C_{1} = p q$ です。この時点で、最大公約数が $1, p, q, p q$ のいずれかにしかならないことが分かります。なので、 $p$ の倍数でないものと、 $q$ の倍数でないものが存在すれば勝ちです。あとは直感でてきとうに見つけてくればいいのです。 $_{n} C_{2},_{n} C_{3}, \dots$ を見てもいいですが、これはあまり筋がよくありません。問題の条件をちゃんと活用してあげましょう。 $_{n} C_{p}$ なんかどうでしょう？
$_{n} C_{p} =_{p q} C_{p} = \frac{p q \cdot (p q - 1) \dots (p (q - 1) + 1)}{p \cdot (p - 1) \dots 1}$
分母、分子に着目すると、どちらも $p$ で $1$ 回だけ割り切れることが分かります。よって $_{n} C_{p}$ は $p$ の倍数ではありません！！
同様に $_{n} C_{q}$ は $q$ の倍数ではないです。また、 $1 < p, q < n$ なので $_{n} C_{p},_{n} C_{q}$ を考えても問題ありません。以上より、証明ができました！

（感想）二項係数の整数問題は難しくなりがちなのですが、思ったより簡単にできました。やっぱり素数は偉大ですね。「素数で割り切れる回数をみる」または「素因数をとる」という操作は少し発展的なテクニックですが慣れれば非常に強力なものになります。解答ではいきなり $_{n} C_{p}$ を考えましたが、 $(p, q) = (2, 3), (3, 5)$ などで実験してからやってもいいと思います。

用語

整数係数多項式全体の集合を $Z [x]$ と表します
例えば $2 x^{2} - 5 x + 3 \in Z [x]$ です

☆2

$f (x) \in Z [x]$ のとき $f (1), f (2), f (3), \dots$ の中には素数でないものが存在することを示せ。ただし $f (x)$ は一次以上とする
（有名題）

思考過程

整数係数の多項式が絡む問題には定石と言っていいほど大切なテクニックが一つあります。それは次のようなものです。

$f (x) \in Z [x]$ のとき,任意の $a, b \in Z$ に対し
$a - b ∣ f (a) - f (b)$
が成り立つ

証明は普通に $f (x)$ をおいてやって計算すればいいです。
$f (x) = c_{0} + c_{1} x + c_{2} x^{2} + c_{3} x^{3} + \dots + c_{n} x^{n}$ とおくと、
$f (a) - f (b) = c_{1} (a - b) + c_{2} (a^{2} - b^{2}) + c_{3} (a^{3} - b^{3}) + \dots + c_{n} (a^{n} - b^{n})$
となり、 $a - b ∣ a^{k} - b^{k}$ なので示せました

さて、どうやって証明しましょうか。直接は無理そうなので、背理法でやってみます。
$f (1), f (2), f (3), \dots$ が全て素数であると仮定しましょう。てきとうに $i$ をとってきて、 $f (i) = p$ です
さっきの補題から、
$p ∣ f (i + p) - f (i)$
であり、 $f (i) (= p)$ はもちろん $p$ の倍数なので、 $f (i + p)$ も $p$ の倍数になります。ここで、仮定から $f (i + p)$ は素数なので、 $f (i + p) = p$ となります！！！！
これを一般化しましょう。補題より、任意の $k > 0$ に対して
$k p ∣ f (i + k p) - f (i) = f (i + k p) - p$
なので、 $p ∣ f (i + k p)$ であり、 $f (i + k p)$ は素数なので $f (i + k p) = p$ です！！
この式の形から $f (x)$ は周期的ですね。僕はここでグラフの形をイメージしました。すると、
$f (i) = f (i + p) = f (i + 2 p) = f (i + 3 p) = \dots = p$
なので、 $f (x) = p$ に無限個の解があることとなり矛盾します！
よって背理法から、示せました。

ちなみに、 $f (x)$ を無理やりずらして定数項を出して考えることもできます。 $f (x + 1) = g (x)$ とおくと、 $g (x) \in Z [x]$ です。示すべきことは、 $g (0), g (1), g (2), \dots$ の中に素数でないものが存在することです。先ほどと同様に背理法でやります。 $g (0), g (1), g (2), \dots$ が全て素数であると仮定します。特に $g (0)$ は素数です。よって素数 $q$ を用いて
$g (x) = a_{m} x^{m} + a_{m - 1} x^{m - 1} + \dots + a_{1} x + q$
となります。 $q ∣ g (k q)$ より $g (k q) = q$ であり、 $g (x) - q = 0$ に無限個の解があるので矛盾です！