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

$f(n)=a×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×3^n+4n^2+3n+1$$であるとき,$f(2)=60=2^2×3×5$であるので$p_1=3$とすれば$$g(n)=2×3^n,h(n)=5^n+4n^2+3n+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\pmod {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×x^{(p_1-1){p^{a_1}}}\equiv x^2\pmod {p^{a_1}}$$がわかる.また任意の正整数$x$に対して$$(2+(p_1-1){p^{a_1}})^x\equiv 2^x\pmod {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) \pmod {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)=\displaystyle \prod_{k=1}^x(p_k-1)p_k^{a_k}$$ただし$x$は正整数である.ここで$p_x$は$\displaystyle 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$について$\displaystyle 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}$で割り切れることから帰納的に示された.以上の結果から$\displaystyle f(2+\sum_{k=1}^{m-1}I(k) )$は少なくとも$p_1,p_2...p_m$で割り切れるので示された.