数学A 合同式 問題 10 解説

方針・初手

$2016$ を素因数分解すると $2016=32\cdot 63$ であり、$32$ と $63$ は互いに素である。

$2^{100}$ は $32$ で割り切れるので、余り $r$ は $32$ の倍数である。一方で、$63$ で割った余りを調べれば、中国剰余定理によって $2016$ で割った余りが決まる。

解法1

求める余りを $r$ とする。まず、

$$ 2016=2^5\cdot 3^2\cdot 7=32\cdot 63 $$

である。

$2^{100}$ は $2^5=32$ で割り切れるから、

$$ r\equiv 0 \pmod{32} $$

である。

次に、$2^{100}$ を $63$ で割った余りを求める。$63=9\cdot 7$ であり、$9$ と $7$ は互いに素である。

まず $9$ について考える。$2^6\equiv 1\pmod{9}$ であり、$100=6\cdot 16+4$ だから、

$$ 2^{100}\equiv 2^4=16\equiv 7 \pmod{9} $$

である。

次に $7$ について考える。$2^3\equiv 1\pmod{7}$ であり、$100=3\cdot 33+1$ だから、

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

である。

したがって、$2^{100}$ を $63$ で割った余り $x$ は

$$ x\equiv 7 \pmod{9},\qquad x\equiv 2 \pmod{7} $$

を満たす。

$7$ で割って $2$ 余る数を $63$ 未満で並べると、

$$ 2,\ 9,\ 16,\ 23,\ 30,\ 37,\ 44,\ 51,\ 58 $$

である。このうち $9$ で割って $7$ 余るものは $16$ なので、

$$ 2^{100}\equiv 16 \pmod{63} $$

である。

よって、求める余り $r$ は

$$ r\equiv 0 \pmod{32},\qquad r\equiv 16 \pmod{63} $$

を満たす。

$r\equiv 0\pmod{32}$ より、$r=32k$ とおける。これを $r\equiv 16\pmod{63}$ に代入すると、

$$ 32k\equiv 16 \pmod{63} $$

である。ここで、

$$ 32\cdot 2=64\equiv 1 \pmod{63} $$

だから、両辺に $2$ をかけて

$$ k\equiv 32 \pmod{63} $$

を得る。したがって、

$$ r=32k\equiv 32\cdot 32=1024 \pmod{2016} $$

である。

$0\leqq 1024<2016$ なので、求める余りは $1024$ である。

解説

法 $2016$ のまま $2^{100}$ を扱うより、$2016=32\cdot 63$ と分けるのが自然である。特に $2^{100}$ は $32$ で割り切れるため、余りが $32$ の倍数になることがすぐ分かる。

残りは $63$ での余りを調べればよい。さらに $63=9\cdot 7$ と分けると、$2^6\equiv 1\pmod{9}$、$2^3\equiv 1\pmod{7}$ を使って指数を小さくできる。

最後に

$$ r\equiv 0 \pmod{32},\qquad r\equiv 16 \pmod{63} $$

を解くことで、$2016$ で割った余りが一意に決まる。

答え

ア：$1024$