問題
を0以上の整数とし，数列を次のように定める。
また，素数を1つとり，をで割った余りをとする。ただし，0をで割った余りは0とする。
(1) 自然数に対し，はをで割った余りと一致することを示せ。
(2) ，の場合に，10以下のすべての自然数に対して，を求めよ。
(3) ある2つの相異なる自然数，に対して，
が成り立ったとする。このとき，が成り立つことを示せ。
出典：東京大学 2014年度 前期日程 第2次学力試験 文系 第4問
方針
(1) は を用いて、和・積の余りが元の数の余りだけで決まることを示す。(2) は を代入して漸化式を余りで順に回し、周期 が現れることを確認する。(3) は と を引き算し、共通の非零余りで割り戻して を導く。
解答
(1)
は を で割った余りであるから である。同様に である。したがって であり、積についても が成り立つ。
漸化式より だから、 を で割った余り、すなわち は、 を で割った余りと一致する。
(2)
なので である。(1) の結果を使って順に計算する。 より である。次に より である。さらに より である。
ここで となった。以後は同じ漸化式で決まるので、余りは を周期として繰り返す。したがって、 以下の自然数 に対して
である。
(3)
仮定より である。 とおくと、 は で割った余りであり、 である。
(1) より であり、同様に である。 だから である。両辺を引いて を得る。
ここで は素数で、 は で割り切れない。したがって である。 はどちらも 以上 以下の整数なので、合同であることから が従う。