トップ› 九州大学› 2016年› 理系第4問

九州大学 2016年理系第4問解説

方針・初手

(1) は割り算の定義である商と余りの関係式を用いるか、合同式を利用して証明する。

(2) は (1) で示した関係性を漸化式として用い、順次計算していく。合同式での負の剰余を活用すると計算が楽になる。

(3) は求める6桁の自然数 $N$ の最上位の数字を $x$、一の位の数字を $y$ とおき、$N$ を $10$ の累乗を用いた式で表す。その後、$13$ を法とする合同式を利用して $x$ と $y$ に関する条件を絞り込む。

(1)

$10^n$ を $13$ で割ったときの商を $q$ とすると、余りは $a_n$ であるから、

$$ 10^n = 13q + a_n $$

と表せる。両辺に $10$ を掛けると、

$$ 10^{n+1} = 10(13q + a_n) = 13(10q) + 10a_n $$

となる。ここで、$10q$ は整数であるから、$10^{n+1}$ を $13$ で割った余りは、$10a_n$ を $13$ で割った余りに等しい。（証明終）

(2)

$10^1 = 10$ を $13$ で割った余りは $10$ であるから、$a_1 = 10$ である。 (1) より、$a_{n+1}$ は $10a_n$ を $13$ で割った余りであるから、順次計算すると以下のようになる。

$10a_1 = 100 = 13 \times 7 + 9$ より、$a_2 = 9$

$10a_2 = 90 = 13 \times 6 + 12$ より、$a_3 = 12$

$10a_3 = 120 = 13 \times 9 + 3$ より、$a_4 = 3$

$10a_4 = 30 = 13 \times 2 + 4$ より、$a_5 = 4$

$10a_5 = 40 = 13 \times 3 + 1$ より、$a_6 = 1$

よって、$a_1=10, a_2=9, a_3=12, a_4=3, a_5=4, a_6=1$ である。

(3)

以下、法を $13$ とする合同式を用いて考える。条件 (i)、(ii) より、自然数 $N$ の最上位（十万の位）の数字を $x$ ($1 \leqq x \leqq 9$)、一の位の数字を $y$ ($0 \leqq y \leqq 9$) とおくと、$N$ は次のように表せる。

$$ N = x \cdot 10^5 + 2016 \cdot 10 + y = 10^5 x + 20160 + y $$

ここで、$10^5$ を $13$ で割った余りは $a_5$ であるから、(2) より

$$ 10^5 \equiv 4 \pmod{13} $$

である。また、$20160 = 13 \times 1550 + 10$ より、

$$ 20160 \equiv 10 \pmod{13} $$

である。

したがって、$N$ は $13$ を法として次のように表せる。

$$ N \equiv 4x + 10 + y \pmod{13} $$

条件 (iii) より、$N$ は $13$ で割り切れるため、$N \equiv 0 \pmod{13}$ である。ゆえに、

$$ 4x + 10 + y \equiv 0 \pmod{13} $$

$$ y \equiv -4x - 10 \equiv -4x + 3 \pmod{13} $$

が成り立つ。 $x$ は $1$ から $9$ の整数であるから、それぞれの $x$ に対して $y$ の条件を調べ、$0 \leqq y \leqq 9$ を満たすものを探す。

$x=1$ のとき: $y \equiv -4 \cdot 1 + 3 = -1 \equiv 12$。$0 \leqq y \leqq 9$ を満たさない。
$x=2$ のとき: $y \equiv -4 \cdot 2 + 3 = -5 \equiv 8$。条件を満たし、$y=8$
$x=3$ のとき: $y \equiv -4 \cdot 3 + 3 = -9 \equiv 4$。条件を満たし、$y=4$
$x=4$ のとき: $y \equiv -4 \cdot 4 + 3 = -13 \equiv 0$。条件を満たし、$y=0$
$x=5$ のとき: $y \equiv -4 \cdot 5 + 3 = -17 \equiv 9$。条件を満たし、$y=9$
$x=6$ のとき: $y \equiv -4 \cdot 6 + 3 = -21 \equiv 5$。条件を満たし、$y=5$
$x=7$ のとき: $y \equiv -4 \cdot 7 + 3 = -25 \equiv 1$。条件を満たし、$y=1$
$x=8$ のとき: $y \equiv -4 \cdot 8 + 3 = -29 \equiv 10$。$0 \leqq y \leqq 9$ を満たさない。
$x=9$ のとき: $y \equiv -4 \cdot 9 + 3 = -33 \equiv 6$。条件を満たし、$y=6$

以上より、条件を満たす $(x, y)$ の組は、

$$ (x, y) = (2, 8), (3, 4), (4, 0), (5, 9), (6, 5), (7, 1), (9, 6) $$

である。これらを $N = x \cdot 10^5 + 20160 + y$ に代入して $N$ を求める。

剰余に関する性質を誘導に乗って活用する、整数問題の典型的な構成である。
合同式を用いると記述が非常に簡潔になるため、積極的に活用したい。
(2) の計算では、負の剰余を考えると計算量が減る。例えば、$10a_2 = 90 \equiv -1 \equiv 12 \pmod{13}$ のように計算できる。
(3) では、位取り記数法の定義に従って数式化し、未知数 $x, y$ の取り得る値の範囲に注意しながら合同式を処理することが重要である。