問題
数列を次のように定める。
(1) を3で割った余りを求めよ。
(2) の最大公約数を求めよ。
方針
解法1
(1)は数列そのものを求めず、 と を3で割った余りだけを追う。 の余りは周期3、 の余りは6項で元に戻るため、表を作って帰納的に周期6を確定する。(2)では、3項の共通約数 が漸化式の差 を割ることを使い、 を2つの具体的な整数の最大公約数の約数に絞る。最後に(1)の結果で3の可能性を除く。
解法2
合同式の状態を の組で追い、同じ状態へ戻ることで周期を厳密に確定する。最大公約数は、共通素因数が2つの連続整数積のどの因子に入りうるかを組合せて3だけに絞る。
解答
解法1
(1)
漸化式を3で割った余りで考えると である。 から順に計算すると
となる。実際、 について であり、上の表が得られる。
ここで の3で割った余りは を3だけ進めると同じである。さらに で に戻るので、以後も同じ計算が繰り返され、 の3で割った余りは周期6である。 であるから であり、表の の欄より である。したがって余りは である。
(2)
とおく。 は と を割るので、 も割る。漸化式より であるから である。
同様に、 は と を割るので も割る。したがって である。
ここで また である。よって であり、 は3の約数である。
一方、(1)より であるから、 は3で割り切れない。したがって も3では割り切れない。ゆえに である。
解法2
(1)
とおく。漸化式から次の状態は現在の だけで決まる。順に
となるので、最初の状態へ6項後に戻る。よって は
を周期6で繰り返す。 だから余りは である。
(2)
とおくと
共通素因数 は、前者の のどちらかと、後者の のどちらかを割る。ところが
したがって可能な素因数は3だけであり、 に含まれる3は1個なので である。(1)より だから
である。