素数の累乗に対する巡回定理

更新日：2022/9/30

本記事では，一般化SNNN数列 $S_{a,b,s}$ の項が素数 $p$ で何回割り切れるかという問題を考える．$p$ が $a$ の素因数である場合については既に議論しているため，ここでは $p$ が $a$ と互いに素である場合について考察する．

まず，具体例としてSNNN数列 $S_{10,7,3}$ における素因数 $p=3$ の個数を観察しよう．素因数分解表を参照して，$S_{10,7,3}(n)$ が $3^k$ の倍数となるような $n$ を $k=1,2,3,\cdots$ について列挙すると，以下のようになる．

得られた数列を観察すると，公差 $3^k$ の等差数列であることが分かる．これは，SNNN数列が $3^k$ を法として基本周期 $3^k$ を持つことを示唆している．この予想は正しいのだろうか．また，他の素因数 $p$ についても同様の表式が得られるだろうか．このことを考察しよう．

素数の累乗を法とする基本周期

$a\neq 1$ であるような一般化SNNN数列 $S=S_{a,b,s}$ と，$a$ と互いに素な奇素数 $p$ を考える．$S$ の法 $p^k$ における基本周期 $u_{p^k}$ は，合同方程式 $S(u) \equiv S(0) \mod{p^k}$ の最小の正の解である（巡回定理の証明を参照）．いま，$a\neq 1$ より $$ S(n) = \frac{Da^n-b}{a-1} $$ であるから，この式を用いて $u_{p^k}$ を求めよう． $$ \begin{align*} S(u) &\equiv S(0) \qquad\mod{p^k} \\ \frac{Da^u-b}{a-1} &\equiv s \qquad\mod{p^k} \\ \frac{Da^u-b-(a-1)s}{a-1} &\equiv 0 \qquad\mod{p^k} \\ \frac{D(a^u-1)}{a-1} &\equiv 0 \qquad\mod{p^k} \\ \nu_p\left(\frac{D(a^u-1)}{a-1}\right) &\ge k \\ \nu_p(a^u-1) &\ge k-\nu_p(D)+\nu_p(a-1) \\ a^u &\equiv 1 \qquad\mod{p^{\max(0,k-\nu_p(D)+\nu_p(a-1))}} \end{align*} $$ $k\le \nu_p(D)-\nu_p(a-1)$ ならば，合同式の法は $p^0=1$ であるから，最小の正の解は $u=1$ である．そうでない場合，最小の正の解は $u=\ord_{p^{k-\nu_p(D)+\nu_p(a-1)}}(a)$ である．さらに $p$ は奇素数であるから，位数定理を用いて $$ \begin{align*} u_{p^k} &= \ord_{p^{k-\nu_p(D)+\nu_p(a-1)}}(a) \\ &= p^{\max(0,k-\nu_p(D)+\nu_p(a-1)-W_p(a))} \cdot \ord_p(a) \\ \end{align*} $$ を得る．以上の結果を定理として以下に記す．

素数冪の巡回定理 $S_{a,b,s}$ を一般化SNNN数列，$p$ を $a$ と互いに素な奇素数とする．$a\neq 1$ ならば，任意の自然数 $k$ に対して $S_{a,b,s}$ は $p^k$ を法とする基本周期 $u_{p^k}$ を持ち， $$ u_{p^k} = \begin{cases} 1 & \text{if } k \le \nu_p(D) - \nu_p(a-1) \\ p^{\max(0,k-\~k_p)} \cdot \ord_p(a) & \text{otherwise} \\ \end{cases} $$ が成り立つ．ただし， $$ \~k_p = \nu_p(D)-\nu_p(a-1)+W_p(a). $$

注意 この定理は $p=2$ では成立しない．$p=2$ の取り扱いについてはこちらの記事を参照されたい．

なお，$W_p(a)\neq 1$ となるような素数（ヴィーフェリッヒ素数）は極めて稀であり，また $D$ や $a-1$ の素因数は高々有限個である．よって，ほとんど全ての素数 $p$ について $\~k_p=1$ である．

演習問題

1. 素数冪の巡回定理において， $p \mid a-1$ ならば $u_{p^k}=p^{\max(0,k-\nu_p(D))}$ となることを証明せよ．
2. 素数冪の巡回定理において $k=1$ としたときの結果が巡回定理と一致することを確認せよ．

素数の累乗で割り切れる項の存在性

素数冪の巡回定理より，$k\ge\~k_p$ の範囲で $u_{p^{k+1}}=p\cdot u_{p^k}$ が成り立つ．このとき，$p$ 個の数 $$ S(n),S(n+u_{p^k}),S(n+2u_{p^k}),\cdots,S(n+(p-1)u_{p^k}) $$ を考えると，これらの数は $p^k$ で割った余りが等しく，$p^{k+1}$ で割った余りは全て異なる．したがって，$S(n) \equiv x \mod{p^k}$ を満たす任意の整数 $x$ は，上記 $p$ 個の数のいずれか1つと法 $p^{k+1}$ で合同である．同様の議論が法 $p^{k+2},p^{k+3},\cdots$ についても成立する．ここで $x=0$ とすれば，次の系を得る．

系 $S_{a,b,s}$ を $a\neq 1$ なる一般化SNNN数列，$p$ を $a$ と互いに素な奇素数とする．$S_{a,b,s}$ 上に $p^{\~k_p}$ の倍数が存在するならば，任意の自然数 $k$ について，$S_{a,b,s}$ 上に $p^k$ の倍数が存在する．

例

SNNN数列 $S_{10,7,3}$ において，$\~k_3=0$ である．$3^0(=1)$ で割り切れるSNNN数として，例えば $3777$ が存在する．よって，任意の自然数 $k$ に対して $3^k$ で割り切れるSNNN数の存在が保証される（参考: 3を素因数にもつSNNN数について）．

演習問題

$487^2$ で割り切れるSNNN数が存在しないことを証明せよ．必要であれば次の事実を用いてよい．

• $487$ は $10$ を底とするヴィーフェリッヒ素数である．
• $\nu_{487}(S_{10,7,3}(450))=1$.