問題#Ⅰ005 ★★☆☆
自然数$n$に対して、$10^n$を$13$で割った余りを$a_n$とおく。$a_n$は$0$から$12$までの整数である。以下の問いに答えよ。
（１）$a_{n+1}$は$10a_n$を$13$で割った余りに等しいことを示せ。
（２）$a_1$、$a_2$、$\cdots$、$a_6$を求めよ。
（３）以下の３条件を満たす自然数$N$をすべて求めよ。
（ⅰ）$N$を十進法で表示したとき$6$桁となる。
（ⅱ）$N$を十進法で表示して、最初と最後の桁の数字を取り除くと$2016$となる。
（ⅲ）$N$は$13$で割り切れる。
《ポイント》
誘導設問に上手く乗りましょう。（１）は漸化式で与えられる数列の剰余に関する問題でよく登場するタイプの設問です。
《解答例》
（１）
$a_n$の定義より、ある自然数$k$、$l$を用いて$$10^n=13k+a_n\tag*{･･･①}$$ $$10^{n+1}=13k+a_{n+1}\tag*{･･･②}$$
と表せる。$①$の両辺に$10$を掛けると
$$10^{n+1}=10 \cdot 13k+10a_{n}\tag*{･･･③}$$となる。$②$と$③$より、$$13l+a_{n+1}=10 \cdot 13k+10a_{n}$$となる。$10a_n$を$13$で割った余りを $r$（$0 \leqq r \leqq 12$）とすると、$10a_n=13k’+r$（$k’$は整数）と表せるから、
$$13l+a_{n+1}=13(10k+k’)+r$$となる。左辺を$13$で割った余りは$a_{n+1}$であり、右辺を$13$で割った余りは$r$であるから、$a_{n+1}=r$ が成立する。故に$a_{n+1}$は$10a_n$を$13$で割った余りに等しい。
□
（２）
（１）で示した事実を利用して計算して、$a_1=10$、$a_2=9$、$a_3=12$、$a_4=3$、$a_5=4$、$a_6=1$ と求められる。
（答）$a_1=10$、$a_2=9$、$a_3=12$、$a_4=3$、$a_5=4$、$a_6=1$
（３）
$$20160=20000+100+60$$より、$20160$を$13$で割った余りは $2a_4+a_2+6a_1$ を$13$で割った余りに等しいから$10$である。
$x$、$y$を $1 \leqq x \leqq 9$、$0 \leqq y \leqq 9$ ･･･（＊）を満たす整数とし、$N=x \cdot 10^5+20160+y$ と置いて$N$を$13$で割った余りを$R$とすると、（２）より $a_5=4$ だから、$R=4x+y+10$ である。（＊）の範囲で$R$を$13$の倍数にする組（$x$、$y$）は
$(2,\,8)$、$(3,\,4)$、$(4,\,0)$、$(5,\,9)$、$(6,\,5)$、$(7,\,1)$、$(9,\,6)$
であるから求める自然数$N$は、
$220168$、$320164$、$420160$、$520169$、$620165$、$720161$、$920166$
である。
（答）$N=220168$、$320164$、$420160$、$520169$、$620165$、$720161$、$920166$
《コメント》
誘導設問が丁寧なので解答の方針には困らないと思います。（３）は誘導設問の結果をうまく利用して解答しましょう。
（出典：九州大学 2016年）