東京大学前期 1979年第3問 (解答解説)

【解答】

漸化式

について考える．初めの4項は

， ， ，

となる．以下，合同式はすべて法4で考える (式2)においてのときとなるので不適である．従ってが必要である．以下各ケースについて個別に考える．

すべてのについてとなることを数学的帰納法で示す．ではである．そこでに対してでの成立を仮定すれば，漸化式(式1)から

となり，でも成立する．従って数学的帰納法によりすべてのでであり，の倍数でない．

すべてのについてとなることを数学的帰納法で示す．では(式2)より成立する．そこでに対してでの成立を仮定すれば，漸化式(式1)から

となり，でも成立する．従って数学的帰納法によりすべてのでである．よって全てのはの倍数でない．

は法4の剰余類での周期数列となることを数学的帰納法で示す．では実際にである．あるについて，での成立を仮定すると，漸化式から

， ，

となる．従って数学的帰納法によりの周期数列となり，の倍数となる項は存在しない．

以上より，必要十分条件は

である．