トップ› 九州大学› 2018年› 文系第2問

九州大学 2018年文系第2問解説

方針・初手

(1) は $2^n$ を $7$ で割った余りの周期性を調べる。具体的に $n=1, 2, 3, \cdots$ を代入して規則性を見つけ、合同式を利用して証明するのが定石である。

(2) は与えられた $2$ 進数の各桁の値を $2$ の累乗を用いて数式として展開し、(1) の結果を利用して $7$ を法とする合同式で処理する。

解法1

(1)

$n=1, 2, 3$ のとき、$2^n$ を $7$ で割った余りをそれぞれ計算する。

$$ 2^1 = 2 \equiv 2 \pmod 7 $$

$$ 2^2 = 4 \equiv 4 \pmod 7 $$

$$ 2^3 = 8 \equiv 1 \pmod 7 $$

$2^3 \equiv 1 \pmod 7$ であるから、自然数 $k$ を用いて $n$ を $3$ で割ったときの余りで場合分けを行う。

(i) $n = 3k$ のとき

$$ 2^{3k} = (2^3)^k \equiv 1^k \equiv 1 \pmod 7 $$

(ii) $n = 3k - 1$ のとき

$$ 2^{3k-1} = 2^{3(k-1)+2} = 2^{3(k-1)} \cdot 2^2 \equiv 1 \cdot 4 \equiv 4 \pmod 7 $$

(iii) $n = 3k - 2$ のとき

$$ 2^{3k-2} = 2^{3(k-1)+1} = 2^{3(k-1)} \cdot 2^1 \equiv 1 \cdot 2 \equiv 2 \pmod 7 $$

以上より、$n$ を $3$ で割った余りが $1, 2, 0$ のとき、それぞれ $2^n$ を $7$ で割った余りは $2, 4, 1$ となる。

(2)

自然数 $m$ は $2$ 進法で $101$ が $6$ 回連続する数であるから、これを累乗の和の形で表す。 $101_{(2)} = 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 5$ であることに注意すると、$m$ は次のように展開できる。

$$ \begin{aligned} m &= 101_{(2)} \cdot 2^{15} + 101_{(2)} \cdot 2^{12} + 101_{(2)} \cdot 2^{9} + 101_{(2)} \cdot 2^{6} + 101_{(2)} \cdot 2^{3} + 101_{(2)} \cdot 2^{0} \\ &= 5 \cdot (2^{15} + 2^{12} + 2^9 + 2^6 + 2^3 + 1) \end{aligned} $$

(1) の結果より、$2^3 \equiv 1 \pmod 7$ であるから、任意の非負整数 $l$ に対して $2^{3l} = (2^3)^l \equiv 1^l \equiv 1 \pmod 7$ が成り立つ。したがって、括弧内の各項はすべて $7$ を法として $1$ と合同になる。

$$ \begin{aligned} m &\equiv 5 \cdot (1 + 1 + 1 + 1 + 1 + 1) \pmod 7 \\ &\equiv 5 \cdot 6 \pmod 7 \\ &\equiv 30 \pmod 7 \\ &\equiv 2 \pmod 7 \end{aligned} $$

よって、$m$ を $7$ で割った余りは $2$ である。

解説

(1) のような累乗の余りを求める問題では、余りが $1$ となる指数を見つけることが鍵となる。合同式の性質を用いて周期性を捉える処理は整数問題の基本である。

(2) では、$2$ 進法表記された数を $10$ 進法の数式として正しく展開できるかが問われている。$101$ というブロックごとにまとめて $5 \cdot 2^{3l}$ の形に整理すると、(1) で得られた $2^3 \equiv 1 \pmod 7$ という性質が直接適用でき、計算量が大幅に削減される。誘導にうまく乗ることが重要である。