問題
を自然数とし，整式を整式で割った余りをとする．このときとは整数であり，さらにそれらをともに割り切る素数は存在しないことを示せ．
出典：京都大学 2013年度 前期日程 第2次学力試験 理系 第3問
方針
で割った余りを考えることは、余りの計算の中で を に置き換えることと同じである。 の余りを と置き、 を掛けてから で整理すると係数の漸化式が得られる。整数性は初期値から従い、共通素因数については漸化式を逆向きに使って、 をともに割る素数が までさかのぼってしまうことを示す。
解答
を で割った余りを と書く。余りの計算では としてよい。 だから、 の余りが であるとき、 の余りは を で整理したものになる。したがって より である。
初期値は の余りから である。漸化式の右辺は整数の加減だけでできているので、帰納的にすべての で は整数である。したがって問題の も整数である。
次に、ある素数 が と をともに割り切ると仮定する。 なら なので不可能である。よって としてよい。
漸化式から であり、また なので である。したがって、 が をともに割り切るなら、 は もともに割り切る。
これを繰り返すと、 は と をともに割り切ることになる。しかし素数が1を割り切ることはない。矛盾である。
以上より、 と は整数であり、それらをともに割り切る素数は存在しない。