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

【解答】

(1)

はで割り切れるが，では割り切れないことを帰納的に示す．

の時は，だから題意は成立するので，以下での成立を仮定し，でも題意が成立することを示す．とおいてを考えると

である． ここでだから仮定より，はで割り切れで割り切れない．一方，よりだから

となってはで割り切れるがで割り切れない．

従ってはで割り切れ，で割り切れないので，でも成立する． 以上から数学的帰納法により題意は題意は示された．

(2)

簡単のため: 「がで割り切れる」，: 「がで割り切れる」とおく． 必要性と十分性をそれぞれ証明する．任意の自然数はと互いに素な自然数とを用いて

とかけることに注意する．この時はとして

となる．

以上から，となり，題意は示された．