問題
数列を次のように定める。
(1) を3で割った余りを求めよ。
(2) の最大公約数を求めよ。
出典：東京大学 2022年度 前期日程 第2次学力試験 文系 第3問
方針
(1)は数列そのものを求めず、 と を3で割った余りだけを追う。 の余りは周期3、 の余りは6項で元に戻るため、表を作って帰納的に周期6を確定する。(2)では、3項の共通約数 が漸化式の差 を割ることを使い、 を2つの具体的な整数の最大公約数の約数に絞る。最後に(1)の結果で3の可能性を除く。
解答
(1)
漸化式を3で割った余りで考えると である。 から順に計算すると
となる。実際、 について であり、上の表が得られる。
ここで の3で割った余りは を3だけ進めると同じである。さらに で に戻るので、以後も同じ計算が繰り返され、 の3で割った余りは周期6である。 であるから であり、表の の欄より である。したがって余りは である。
(2)
とおく。 は と を割るので、 も割る。漸化式より であるから である。
同様に、 は と を割るので も割る。したがって である。
ここで また である。よって であり、 は3の約数である。
一方、(1)より であるから、 は3で割り切れない。したがって も3では割り切れない。ゆえに である。