倍数法則によるSNNN素数の有限性証明の不可能性
更新日：2022/9/30
倍数法則による素数項の有限性証明
前回の記事ではSNNN数の倍数法則を調べ，巡回定理を導いたが，その動機はSNNN素数の所在を絞り込むことにあった．このようなことは一般の $S_{a,b,s}$ に対して考えられるのだが，中には倍数法則によって素数項の有限性が証明される場合が存在する．以下にその一例を示す．
例
11進法で $3_{(11)},37_{(11)},377_{(11)},3777_{(11)},\cdots$ と表される数（11進SNNN数）からなる数列 $S_{11,7,3}$ を考える．この数列に関して，次のような倍数法則が知られている（$k$ は自然数）．
- $S_{11,7,3}(2k)$ は $3$ の倍数．
- $S_{11,7,3}(2k+1)$ は $2$ の倍数．
このことから，$S_{11,7,3}$ の項は全て $2$ または $3$ の倍数であることが分かる．したがって，$S_{11,7,3}$ 上に存在する可能性のある素数は $2$ と $3$ の2個のみである．
それでは，SNNN数列 $S_{10,7,3}$ についても同様にして素数項の有限性が示されることがあるだろうか．そのようなことはない，というのが本記事の主定理である．以下，この事実を証明する．
注意 本記事で証明する事実は，倍数法則によるSNNN素数の有限性証明の不可能性のみであり，他の方法でSNNN素数の有限性が証明される可能性は否定できない．
示すべき命題
上記の $S_{11,7,3}$ の例では，全ての項が $2$ または $3$ の倍数であるという事実が素数項の有限性証明の鍵となった．一般に，一般化SNNN数列 $S_{a,b,s}$ が
① ある有限個の素数 $p_1,p_2,\cdots,p_m$ が存在して，
② $S_{a,b,s}$ の全ての項が，
③ $p_1,p_2,\cdots,p_m$ のいずれかの倍数である．
という条件を満たすならば，$S_{a,b,s}$ の素数項は有限個（$m$ 個以下）である．
この証明を成立させないためには，前提条件の否定命題を考えればよい．すなわち，
①' 任意の有限個の素数 $p_1,p_2,\cdots,p_m$ に対して，
②' ある $S_{10,7,3}$ の項（SNNN数）が存在して，
③' $p_1,p_2,\cdots,p_m$ の全てで割り切れない．
という命題を示すことが目標である．
証明
以下，SNNN数列 $S_{10,7,3}$ を $S$ と表記する．
補題 $n$ を自然数，$p$ を $10$ と互いに素な素数とする．このとき， $$ n\equiv -1\enspace(\text{mod }u_p) \implies S(n)\nequiv 0\enspace(\text{mod }p). $$
証明
巡回定理より，$S(u_p-1)\nequiv 0\mod{p}$ を示せば十分である．$u_p$ の表式によって場合分けを行う．
$u_p=\ord_p(a)$ の場合
以下，特に断らない限り合同式の法は $p$ とする．$S(u_p-1)\equiv 0$ を仮定すると $$ \begin{align*} \frac{Da^{\ord_p(a)-1}-b}{a-1} &\equiv 0\\ Da^{\ord_p(a)}-ab &\equiv 0\\ D-ab &\equiv 0\\ (a-1)s+b-ab &\equiv 0\\ (a-1)(s-b) &\equiv 0\\ \end{align*} $$ $a\nequiv 1$ であるから $s-b\equiv 0$．すなわち $p$ は $s-b\,(=-4)$ の約数であるから $p=2$．しかしこれは $10$ と互いに素でないため不適である．したがって $S(u_p-1)\equiv 0$ を満たす $p$ は存在しない．
$u_p=p$ の場合
$a-1\,(=9)$ の約数，すなわち $p=3$ が該当する．このとき $S(u_p-1)\equiv S(2)\equiv 377\nequiv 0\mod{3}$．
$u_p=1$ の場合
$D\,(=34)$ の約数，すなわち $p=17$ が該当する．このとき $S(u_p-1)\equiv S(0)\equiv 3\nequiv 0\mod{17}$．$\blacksquare$
定理 任意の有限個の素数 $p_1,p_2,\cdots,p_m$ に対して，そのいずれでも割り切れないSNNN数が存在する．
証明
素数 $2$ と $5$ がSNNN数を割り切らないことは自明であるから，$p_1,p_2,\dots,p_m$ は $2$ と $5$ を含まないと仮定してよい．すると補題より $$ \begin{align*} n &\equiv -1 \mod{u_{p_1}} &&\implies& S(n) &\nequiv 0 \mod {p_1} \\ n &\equiv -1 \mod{u_{p_2}} &&\implies& S(n) &\nequiv 0 \mod {p_2} \\ &&&\enspace\enspace\,\vdots \\ n &\equiv -1 \mod{u_{p_m}} &&\implies& S(n) &\nequiv 0 \mod {p_m} \\ \end{align*} $$ が成り立つ．ここで自然数 $X\coloneqq u_{p_1}u_{p_2}\cdots u_{p_m}-1$ を考えると，$n=X$ は $m$ 個の条件節全てを満たすから，$S(X)$ はどの $p_i\;(1\le i\le m)$ でも割り切れない．$\blacksquare$
SNNN素因数の無限性
以上で本記事の目標は果たされたが，上記の定理はもう一つ興味深い事実を主張している．それは，SNNN数の素因数（SNNN素因数）が無数に存在するという事実である．このことは，$p_1,p_2,\cdots,p_m$ をSNNN素因数としたとき，そのいずれでも割り切れないSNNN数が新たな素因数 $p_{m+1}$ を持つことから分かる．
余談 ちなみに，ここまでの議論において素数の無限性は一切使っていないため，この定理は単に素数の無限性の証明としても通用する．
なお，本記事の証明はSNNN数列 $S_{10,7,3}$ に特有のものであり，一般の $S_{a,b,s}$ に適用できるものではない．一方で，「素因数が無数に存在する」という性質そのものは，ほとんど全ての一般化SNNN数列において成り立つことが知られている．この事実はSNNN素因数定理と呼ばれ，その証明には本記事と全く異なるアプローチを要する．
