数列\(a_n\)を次のように定義する。以下の1、2を示せ。 \[\begin{align*}
a_1=1, a_{n+1}=2a_n+1
\end{align*}\]
1. 任意の奇素数は数列\(a_n\)のある数の素因数である。
2. 任意の奇数は数列\(a_n\)のある数の約数である。

解答

数列\(a_n\)の一般項を求めると、 \[\begin{align*}
a_{n}=1+2+2^2+2^3+ \cdots +2^{n-1}=2^n-1 \ .
\end{align*}\] [1の解答]
\(p\)を奇素数とする。2と\(p\)は互いに素なので、フェルマーの小定理より、 \[\begin{align*}
2^n &\equiv 1 \ ({\rm mod} \ p) \\
2^n-1 &\equiv 0 \ ({\rm mod} \ p) \ .
\end{align*}\] [2の解答]
\(k\)を任意の奇数とする。自然数を\(k\)で割った余りは1〜\(k-1\)のいずれかになるので、鳩の巣原理より\(a_m, \ a_n\)を\(k\)で割った余りが等しくなるような\(m<n\)が存在する。
\(a_n-a_m\)を計算すると、 \[\begin{align*}
a_n-a_m &= 2^m(2^{n-m}-1) \\
&= 2^ma_{n-m} \\
&\equiv 0 \ ({\rm mod} \ k) \ .
\end{align*}\] \(2^m\)と\(k\)は互いに素であるから\(a_{n-m}\)は\(k\)の倍数。
別解として、数論におけるオイラーの定理や剰余環の知識を使うとよりシンプルに解けます。

この記事を共有