\(r\) を \(0\) 以上の整数とし, 数列 \(\{ a _ n \}\) を次のように定める. \[\begin{align} & a _ 1 = r , \quad a _ 2 = r+1 , \\ & a _ {n+2} = a _ {n+1} ( a _ n +1 ) \quad ( n = 1 , 2 , 3 , \cdots ) \end{align}\] また, 素数 \(p\) を \(1\) つとり, \(a _ n\) を \(p\) で割った余りを \(b _ n\) とする. ただし, \(0\) を \(p\) で割った余りは \(0\) とする.
(1) 自然数 \(n\) に対し, \(b _ {n+2}\) は \(b _ {n+1} ( b _ n +1 )\) を \(p\) で割った余りと一致することを示せ.
(2) \(r=2\) , \(p=17\) の場合に, \(10\) 以下のすべての自然数 \(n\) に対して, \(b _ n\) を求めよ.
(3) ある \(2\) つの相異なる自然数 \(n , m\) に対して, \[ b _ {n+1} = b _ {m+1} \gt 0 , \quad b _ {n+2} = b _ {m+2} \] が成り立つとする. このとき \(b _ n = b _ m\) が成り立つことを示せ.
【 解 答 】
(1)
\(a _ n\) を \(p\) で割った商を \(q _ n\) とおけば, \(a _ n = p q _ n +b _ n\) と表せる.
\(b _ {n+1} ( b _ n +1 )\) を \(p\) で割った商を \(q'\) , 余りを \(r'\) とおくと
\[\begin{align}
a _ {n+2} & = ( p q _ {n+1} +b _ {n+1} ) ( p q _ n +b _ n +1 ) \\
& = p \left\{ p q _ {n+1} q _ n +q _ {n+1} ( b _ n +1 ) +q _ n b _ {n+1} +q' \right\} +r'
\end{align}\]
つまり, \(a _ {n+2}\) を \(p\) で割った余りは \(r'\) であるから
\[
b _ {n+2} = r'
\]
よって, 題意は示された.
(2)
条件より \[ b _ 1 = \underline{2} , \quad b _ 2 = \underline{3} \] (1) の結果を用いれば \[\begin{align} b _ 2 ( b _ 1 +1 ) & = 3 ( 2+1 ) =9 & \text{∴} \quad b _ 3 = \underline{9} \\ b _ 3 ( b _ 2 +1 ) & = 9 ( 3+1 ) = 36 = 17 \cdot 2 +2 & \text{∴} \quad b _ 4 = \underline{2} \\ b _ 4 ( b _ 3 +1 ) & = 2 ( 9+1 ) = 20 = 17 +3 & \text{∴} \quad b _ 5 = \underline{3} \end{align}\] あとは, 繰返しとなるので \[ b _ 6 = \underline{9} , \ b _ 7 = \underline{2} , \ b _ 8 = \underline{3} , \ b _ 9 = \underline{9} , \ b _ {10} = \underline{2} \]
(3)
条件より, \(b _ {n+1} = b _ {m+1} = k \gt 0\) , \(b _ {n+2} = b _ {m+2} = \ell\) ... [1] とおく.
ある整数 \(c _ n , c _ m\) をとれば
\[\begin{align}
b _ {n+2} & = b _ {n+1} ( b _ n +1 ) -p c _ n \\
b _ {m+2} & = b _ {m+1} ( b _ m +1 ) -p c _ m
\end{align}\]
と表せる.
[1] を代入して
\[\begin{align}
\ell & = k ( b _ n +1 ) -p c _ n \\
\ell & = k ( b _ m +1 ) -p c _ m
\end{align}\]
辺々を引いて, 整理すると
\[
k \left( b _ n -b _ m \right) = p \left( c _ n -c _ m \right)
\]
右辺は \(p\) で割り切れるので, 左辺も \(p\) で割り切れる.
\(0 \lt k \lt p\) なので, \(b _ n -b _ m\) が \(p\) で割り切れる, つまり \(b _ n\) と \(b _ m\) は \(p\) で割った余りが等しい.
よって, 題意は示された.