問題#Ⅰ011 ★★☆☆
$a_1=1$、$a_2=1$、$a_{n+2}=a_{n+1}+a_{n} \ (n=1,2,3,\cdots)$ で定められる数列$\{a_n\}$について、以下の問いに答えよ。
（１）$a_n$が$2$の倍数となるような自然数$n$の条件を求めよ。
（２）$a_n$が$3$の倍数となるような自然数$n$の条件を求めよ。
（３）$a_n$が$12$の倍数となるような自然数$n$の条件を求めよ。
《ポイント》
フィボナッチ数列に関する問題です。倍数の判定は合同式で考えるのが良いでしょう。倍数の項が現れる周期を求めるには、$a_1$と$a_2$の剰余と等しくなるような連続する$2$項を見つければOKです。
《解答例》
（１）
$a_1=1$、$a_2=1$ は奇数であるから$a_3$は偶数となる。$a_4$は$a_2$（奇数）と$a_3$（偶数）の和だから奇数となり、$a_5$は$a_3$（偶数）と$a_4$（奇数）の和だから奇数となる。故に$a_4$以降からは「奇数、奇数、偶数」の繰り返しとなるから、$a_n$が$2$の倍数となるような自然数$n$の条件は
「$n$が$3$の倍数であること」
となる。
（答）$n$が$3$の倍数であること
（２）
以下、合同式を$\bmod{3}$ として考える。漸化式より、$$a_{n+2} \equiv a_{n+1}+a_{n} \ (n=1,2,3,\cdots)$$が成り立つことに注意する。
$a_1 \equiv 1$、$a_2 \equiv 1$ より、$$a_3 \equiv 1+1=2$$ $$a_4 \equiv 2+1=3 \equiv 0$$ $$a_5 \equiv 0+2=2$$ $$a_6 \equiv 2+0=2 \equiv 0$$ $$a_7 \equiv 2+2=4 \equiv 1$$ $$a_8 \equiv 1+2=3 \equiv 0$$ $$a_9 \equiv 0+1=1$$ $$a_{10} \equiv 1+0=1$$となるので、$a_n$を$3$で割った余りは周期$8$で繰り返し、$a_n$は周期$4$で$3$の倍数となる。よって$a_n$が$3$の倍数となるような自然数$n$の条件は
「$n$が$4$の倍数であること」
となる。
（答）$n$が$4$の倍数であること
（３）
$a_n$が$12$の倍数となるような自然数$n$の条件を求めるが、ここで $12=2^2 \cdot 3$ であり、$2$と$3$は互いに素なので、（２）の結果を利用すれば、$a_n$が$4$の倍数となるような自然数$n$の条件を求めれば十分である。
以下、合同式を$\bmod{4}$ とし、（２）と同様に考える。
$a_1 \equiv 1$、$a_2 \equiv 1$ より、$$a_3 \equiv 1+1=2$$ $$a_4 \equiv 2+1=3$$ $$a_5 \equiv 3+2=5 \equiv 1$$ $$a_6 \equiv 1+3 \equiv 0$$ $$a_7 \equiv 0+1=1$$ $$a_8 \equiv 1+0=1$$となるので、$a_n$を$4$で割った余りは周期$6$で繰り返し、$a_n$は$n$が$6$の倍数となるときに$4$の倍数となる。よって$a_n$が$12$の倍数となるような自然数$n$の条件は
「$n$が$12$の倍数であること」
となる。
（答）$n$が$12$の倍数であること
《コメント》
（３）では最終的に、$n$が$4$の倍数かつ$6$の倍数となる条件が求める答えとなりますが、誤って「$n$が$24$の倍数であること」としてしまわないように注意しましょう。合成数を法としたときの剰余は素因数ごとに考えるのが常道です。当サイトの「創作整数問題」シリーズにも似たような考え方を利用する問題が多く存在しますので、演習がてら覗いてみて下さい。
（出典：有名問題（創作整数問題#16））