指数関数と正整数係数多項式の和で表せる関数fはほとんどの場合においていくらでも多くの素因数を持つ!

544

指数関数と正整数係数多項式の和で表せる関数 $f (n)$ (例えば $f (n) = 2^{n} + 1, 2 \times 5^{n} + n^{3} + 2 n^{2} + 3 n + 1, n^{1234} + 3$ など)はある正整数 $a, b$ が存在して $f (n) = a \times b^{n}$ と表せない時,任意の正整数 $m$ に対して,ある正整数 $N$ が存在して $f (N)$ が $m$ 種類以上の相異なる素数で割り切れます.

$f (n) = a \times b^{n}$ と表せないとしよう. $f (2) > 1$ のある素因数を取って $p_{1}$ とする. $f$ の全ての項が指数関数であり,かつそれらの底をすべて割り切るような素数 $p$ が存在するとき, $f$ を $p^{n}$ で割れば結局そのようなものが存在しない場合に帰着される.ここで $f (n) = g (n) + h (n)$ なる関数 $g, h$ を次のように定める. $f$ の項の内,指数関数の底が $p_{1}$ で割り切れるような項の和を $g$ ,それ以外の項の和を $h$ とする.また先ほどの結果より $h$ は $0$ と恒等でないとしてよい.(たとえば $f (n) = 5^{n} + 2 \times 3^{n} + 4 n^{2} + 3 n + 1$ であるとき, $f (2) = 60 = 2^{2} \times 3 \times 5$ であるので $p_{1} = 3$ とすれば $g (n) = 2 \times 3^{n}, h (n) = 5^{n} + 4 n^{2} + 3 n + 1$ である.)ここで $v_{p_{1}} (g (n)) ≧ n$ である.ここで $a_{1} > v_{p_{1}} (h (2))$ なる $a_{1}$ をひとつとってくればフェルマーの小定理から任意の $p_{1}$ で割り切れない正整数 $x$ に対して $x^{p_{1} - 1} \equiv 1 (\mod p_{1})$ であり,ここからLTEの補題より $v_{p_{1}} (x^{(p_{1} - 1) p^{a_{1}}} - 1) ≧ a_{1} + 1$ (これは $p_{1} = 2$ でも成立)であり,ここから $x^{2 + (p_{1} - 1) p^{a_{1}}} \equiv x^{2} \times x^{(p_{1} - 1) p^{a_{1}}} \equiv x^{2} (\mod p^{a_{1}})$ がわかる.また任意の正整数 $x$ に対して $(2 + (p_{1} - 1) p^{a_{1}})^{x} \equiv 2^{x} (\mod p^{a_{1}})$ が左辺の二項展開からわかるので $a > v_{p_{1}} (h (2))$ より $v_{p_{1}} (h (2)) = v_{p_{1}} (h (2 + (p_{1} - 1) p^{a_{1}}))$ である.また
$v_{p_{1}} (g (2 + (p_{1} - 1) p_{1}^{a_{1}})) ≧ a_{1} > v_{p_{1}} (h (2))$ である.これらから $f (2 + (p_{1} - 1) p_{1}^{a_{1}}) \equiv h (2) (\mod p^{a_{1}})$ が分かり,よって
$v_{p_{1}} (f (2 + (p_{1} - 1) p_{1}^{a_{1}})) = v_{p_{1}} (h (2))$ が成り立ち,また $p_{1}^{v_{p_{1}} (h (2))} ≦ h (2) ≦ f (2) < f (2 + (p_{1} - 1) p_{1}^{a_{1}})$ より $f (2 + (p_{1} - 1) p_{1}^{a_{1}})$ は $p_{1}$ でちょうど $v_{p_{1}} (h (2))$ 回割り切れる $p_{1}^{v_{p_{1}} (h (2))}$ より大きい整数であるので, $p_{1}$ でない素因数をもつ.以上の議論をふまえて関数 $I (n)$ を次のように定義しよう. $I (x) = \prod_{k = 1}^{x} (p_{k} - 1) p_{k}^{a_{k}}$ ただし $x$ は正整数である.ここで $p_{x}$ は $f (2 + \sum_{k = 1}^{x - 1} I (k))$ を割り切る素数であって, $p_{1}, p_{2} . . . p_{x - 1}$ と異なるものである.またここで $f (n) = g_{k} (n) + h_{k} (n)$ なる関数 $g_{k}, h_{k}$ を次のように定める. $f$ の項の内,指数関数の底が $p_{k}$ で割り切れるような項の和を $g_{k}$ ,それ以外の項の和を $h_{k}$ とする.このとき $a_{k}$ は $a_{k} > v_{p_{k}} (h_{k} (2))$ なる正整数である.ここでについて,このような $p_{n}$ が任意の正整数 $n$ に対して取れることを証明しよう.まず $p_{1}$ については $f (2) > 1$ より自明である.ここで $n = x$ について $v_{p_{t}} (f (2 + \sum_{k = 1}^{x - 1} I (k))) = v_{p_{t}} (h_{t} (2 + \sum_{k = 1}^{x - 1} I (k)))$ が $t = 1, 2, . . ., x$ で成り立つと仮定する.この時先ほどの議論と同様に $v_{p_{t}} (h_{t} (2 + \sum_{k = 1}^{x - 1} I (k))) = v_{p_{t}} (h_{t} (2 + (\sum_{k = 1}^{x - 1} I (k)) + I (x)))$ また $v_{p_{t}} (g_{t} (2 + (\sum_{k = 1}^{x - 1} I (k)) + I (x))) > a_{t}$ が $t = 1, 2, . . ., x$ についてわかるので $v_{p_{t}} (h_{t} (2 + (\sum_{k = 1}^{x - 1} I (k)) + I (x))) = v_{p_{t}} (f (2 + (\sum_{k = 1}^{x - 1} I (k)) + I (x)))$ が同様に $t = 1, 2, . . . x$ についてわかる.よって $v_{p_{t}} (f (2 + (\sum_{k = 1}^{x - 1} I (k)))) = v_{p_{t}} (f (2 + \sum_{k = 1}^{x} I (k)))$ が $t = 1, 2, . . . x$ について成り立ち,かつ $f (2 + \sum_{k = 1}^{x - 1} I (k)) < f (2 + \sum_{k = 1}^{x} I (k))$ よりこれは $p_{1}, p_{2} . . . p_{x}$ でない素因数 $p_{x + 1}$ で割り切れることから帰納的に示された.以上の結果から $f (2 + \sum_{k = 1}^{m - 1} I (k))$ は少なくとも $p_{1}, p_{2} . . . p_{m}$ で割り切れるので示された.