数学A n進法 問題 4 解説

方針・初手

$2^3=8$ は $7$ で割ると余りが $1$ である。したがって、$2^n$ を $7$ で割った余りは、指数 $n$ を $3$ で割った余りだけで決まる。

また、2進法で $101$ が繰り返されている数は、$101_{(2)}=5$ を $3$ 桁ごとに並べた数として扱うとよい。

解法1

まず、

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

である。よって、自然数 $n$ を $3$ で割った商と余りを用いて

$$ n=3q+r \quad (r=0,1,2) $$

と表すと、

$$ 2^n=2^{3q+r}=(2^3)^q2^r\equiv 1^q2^r\equiv 2^r \pmod{7} $$

となる。

したがって、$r$ の値ごとに

(i)

$n\equiv 0\pmod{3}$ のとき

$$ 2^n\equiv 2^0=1 \pmod{7} $$

(ii)

$n\equiv 1\pmod{3}$ のとき

$$ 2^n\equiv 2^1=2 \pmod{7} $$

(iii)

$n\equiv 2\pmod{3}$ のとき

$$ 2^n\equiv 2^2=4 \pmod{7} $$

である。

次に、$m$ は

$$ m=101101101101101101_{(2)} $$

である。これは $101$ が $6$ 回連続しているので、

$$ m=101_{(2)}\times \left(2^{15}+2^{12}+2^9+2^6+2^3+1\right) $$

と表せる。

ここで、

$$ 101_{(2)}=2^2+1=5 $$

であるから、

$$ m=5\left(2^{15}+2^{12}+2^9+2^6+2^3+1\right) $$

となる。

各指数はすべて $3$ の倍数である。$2^3\equiv 1\pmod{7}$ より、

$$ 2^{15}\equiv 2^{12}\equiv 2^9\equiv 2^6\equiv 2^3\equiv 1 \pmod{7} $$

である。したがって、

$$ m\equiv 5(1+1+1+1+1+1)=30\equiv 2 \pmod{7} $$

となる。

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

解法2

2進法で $3$ 桁ごとに区切ると、これは $8$ 進法の表示に直せる。

$$ 101_{(2)}=5_{(8)} $$

であるから、

$$ 101101101101101101_{(2)}=555555_{(8)} $$

である。

したがって、

$$ m=5\cdot 8^5+5\cdot 8^4+5\cdot 8^3+5\cdot 8^2+5\cdot 8+5 $$

と表せる。

ここで、

$$ 8\equiv 1 \pmod{7} $$

だから、

$$ 8^k\equiv 1 \pmod{7} $$

である。よって、

$$ m\equiv 5+5+5+5+5+5=30\equiv 2 \pmod{7} $$

となる。

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

解説

この問題の中心は、$2^3\equiv 1\pmod{7}$ に気づくことである。これにより、$2^n$ の余りは $n$ を $3$ で割った余りだけで決まる。

また、2進法で $101$ が繰り返される数は、$3$ 桁ごとのまとまりとして見ると扱いやすい。$101_{(2)}=5$ であり、さらに $2^3=8\equiv 1\pmod{7}$ なので、各まとまりが合同式の上では同じ寄与をする。

解法2のように、$3$ 桁ごとに区切って $8$ 進法に直すと、$8\equiv 1\pmod{7}$ を直接使えるため、計算がさらに短くなる。

答え

(1)

$$ \begin{cases} 1 & (n\equiv 0\pmod{3})\\ 2 & (n\equiv 1\pmod{3})\\ 4 & (n\equiv 2\pmod{3}) \end{cases} $$

(2)

$$ 2 $$