問題
は正の整数とする。をで割った余りをとおく。
(1) 数列，，，は
を満たすことを示せ。
(2) に対して，，は共に正の整数で，互いに素であることを証明せよ。
出典：東京大学 2002年度 前期日程 第2次学力試験 文理共通 文科第2問・理科第2問
方針
余りだけを追うため、 と見て計算する。 なので、余り にxを掛けてから を に置き換えれば漸化式が出る。(2)は初期値 を確認し、正の整数性は漸化式で、互いに素であることは公約数が一段前の も割ることから帰納法で示す。
解答
(1)
を で割った余りが であるから、ある多項式 を用いて と書ける。両辺にxを掛けると である。したがって、 を で割った余りは、 を同じ式で割った余りに等しい。
ここで とみなして余りを計算すれば である。よって
である。したがって を得る。
(2)
まず では、 を で割った余りは である。したがって であり、どちらも正の整数で互いに素である。
次に、ある で が正の整数であるとする。このとき(1)より であるから、 も正の整数である。よって帰納法により、すべての で は正の整数である。
互いに素であることを示す。 が互いに素であると仮定し、 を の公約数とする。このとき である。したがって である。つまり は の公約数である。仮定より は互いに素なので である。
よって も互いに素である。初期値 から帰納法により、すべての正の整数 について は互いに素である。
別解。互いに素の部分は と見て、共通に割る数は差を取ることで も割る、と考えてもよい。これは最大公約数を保つ変形であり、前の組へ戻せることが本質である。