５番 r を 0 以上の整数とし、数列 {an } を次のように定める。 a1 = r, a2 = r + 1, an+2 = an+1 (an + 1) (n = 1, 2, 3, · · ·) また、素数 p を１つとり、an を p で割った余りを bn とする。ただし、0 を p で割った余りは 0 とする。 (1) 自然数 n に対し、bn+2 は bn+1 (bn + 1) を p で割った余りと一致することを示せ。 (2) r = 2, p = 17 の場合に、10 以下のすべての自然数 n に対して、bn を求めよ。 (3) ある２つの異なる自然数 n, m に対して、 bn+1 = bm+1 > 0, bn+2 = bm+2 が成り立ったとする。このとき、bn = bm が成り立つことを示せ。 (4) a2 , a3 , a4 , · · · · · · に p で割り切れない数が現れないとする。このとき、a1 も p で割り切れないことを示せ。【2014 東京大学理系】解答 (1) an+1 = pQ1 + bn+1 , an = pQ2 + bn とおくと、 an+2 = an+1 (an + 1) = (pQ1 + bn+1 ) (pQ2 + bn + 1) = pM + bn+1 (bn + 1) ∴ bn+2 ≡ bn+1 (bn + 1) (modp) よって、bn+2 は bn+1 (bn + 1) を p で割った余りと一致する。 (2) r = 2, p = 17 の場合。(1) の結果を利用して、下表を得る。 n 1 2 3 4 5 6 7 8 9 10 bn 2 3 9 2 3 9 2 3 9 2 (3) bn+1 = bm+1 = r1 > 0, bn+2 = bm+2 = r2 のとき、 r2 ≡ r1 (bn + 1) (modp) r2 ≡ r1 (bm + 1) (modp) c Darumafactory -1- RadicalMath r1 (bn + 1) ≡ r1 (bm + 1) (modp) ⇔ r1 (bn − bm ) ≡ 0 (modp) ここに、0 < r1 < p, p, r は互いに素であるから、 bn − bm ≡ 0 (modp) ⇔ bn = bm (4) a2 , a3 , a4 , · · · · · · に p で割り切れない数が現れないとする, すなわち、 \ 0 (n = 2, 3, 4, · · · · · ·) bn = である。bn は有限個の値 bn = 1, 2, 3, · · · , p − 1 をとるから、隣接２項の値の組 (bk+1 , bk+2 ) の取り方は、(k − 1)2 通りの有限個しかない。したがって、ある異なる２つの自然数 k, j(k > j) があって、 (bk+1 , bk+2 ) = (bj+1 , bj+2 ) , k > j となる。よって、(3) の結果より、 bk = bj \ 0 であるから、b1 = \ 0 となる。これを繰り返して、b1 = bk−j+1 を得る。bk−j+1 = c Darumafactory -2- RadicalMath