九州大学 2018年度文系数学前期第2問解答・解説

問題

以下の問いに答えよ。

(1) $n$ を自然数とするとき， $2^{n}$ を7で割った余りを求めよ。

(2)自然数 $m$ は，2進法で101が6回連続する表示

101101101101101101_{(2)}

をもつとする。 $m$ を7で割った余りを求めよ。

出典：九州大学 2018年度前期日程第2次学力試験文系前期第2問

$2^{3} \equiv 1 (mod 7)$ から余りの周期が3であることを使う。(2) は2進表示を3桁ずつの $101$ に区切り、各ブロックが8進法の1桁 $5$ に対応すると見る。

(1) は $2^{n + 3} - 2^{n} = 7 \cdot 2^{n}$ を用いて周期性を直接示す。(2) は2進表示で1が立っている桁を指数 $3 j$ と $3 j + 2$ に分け、そのまま合同式で足す。

2^{1} \equiv 2, 2^{2} \equiv 4, 2^{3} \equiv 1 (mod 7)

であり、以後は周期3で繰り返す。したがって

n (mod 3) 2^{n} (mod 7) 122401

となる。

$10 1_{(2)} = 5$ であり、3桁のずれは $2^{3} = 8$ 倍に対応する。よって

m = 5 (8^{5} + 8^{4} + 8^{3} + 8^{2} + 8 + 1)

である。 $8 \equiv 1 (mod 7)$ だから

m \equiv 5 (1 + 1 + 1 + 1 + 1 + 1) = 30 \equiv 2 (mod 7)

となる。求める余りは $2$ である。

任意の自然数 $n$ に対して

2^{n + 3} - 2^{n} = 7 \cdot 2^{n}

だから、 $2^{n + 3}$ と $2^{n}$ は7で割った余りが等しい。最初の3項は

2, 4, 1

なので、 $n \equiv 1, 2, 0 (mod 3)$ の順に余りは $2, 4, 1$ である。

右端のブロックを $j = 0$ とすると、各 $101$ で1が立つ桁は $3 j$ と $3 j + 2$ である。したがって

m = j = 0 \sum 5 (2^{3 j + 2} + 2^{3 j})

となる。 $2^{3} \equiv 1 (mod 7)$ より、各 $j$ について

2^{3 j + 2} + 2^{3 j} \equiv 4 + 1 = 5 (mod 7)

である。6ブロックを足して

m \equiv 6 \cdot 5 = 30 \equiv 2 (mod 7)

を得る。したがって余りは $2$ である。