東京大学 前期 2014年 第5問 (解答解説)

【解答】

与えられた漸化式

について考える．

(1)

合同式の法をとすると(式1)の第二式に第三式を代入して

だから題意は示された．

(2)

だから，である． 以下(式3)を繰り返し用いて

だから，以降のくり返しとなるから，

である．

(3)

題意を背理法で示す．すなわち，と仮定して題意の条件

が成立するかどうかを調べる．

対称性からとしてよい．漸化式(式3)および条件(式6)から

が成り立つ．辺々引き算して

である．ここで(式6)より

であり，また仮定のより

である．が素数であることと合わせて(式6)は成立せずに矛盾する． 以上より背理法によりである．

(4)

題意より任意のに対して，

である． さらにこの時，（）はの高々個の値しかとらないことから，連続する2項のならびは高々通りしか存在せず，鳩の巣原理から

を満たす異なるがある（とする）．

この時(3)からとなり，再び，に(3)を適用して，となる．これをくり返して，より，

となるから，，つまりはで割り切れない．

【別解】

(4)

[解]と同様に，

を満たすについて考える．ここで[解]ではのもののみを考えていたが，あえてを許容することでも証明できるのでやってみよう．

が最小であるものについて考えると，であり，がで割り切れないことから，したがってである．

と仮定すると，が定義され，かつだから，(3)よりとなり，はの最小性に反する．したがってで，

（かつがで割り切れない）だから，はで割り切れない．