2016年 早稲田大学
\( 2^{100} \) を \( 2016 \) で割った余りを求めよ。
解説
合同式を使う問題です。以下の性質を使います。
合同式の性質
\( a \equiv b ( \mod m ) \) のとき、\( a^n \equiv b^n \) が成り立つ。\( n \) は自然数とする。
解答
\( 2016 \) で割った余りの合同式（ \( \mod 2016 \) ）を考える。
\begin{eqnarray}
2^{11} &=& 2048 \equiv 32 = 2^5 \\
2^{100} &=& 2^{11 \times 9 + 1} = 2 \cdot ( 2^{11} )^9 \\
&\equiv& 2 \cdot ( 2^5 )^9 = 2^{46} = 2^{11 \times 4 + 2 } = 2^2 \cdot ( 2^{11} )^4 \\
&\equiv& 2^2 \cdot (2^5)^4 = 2^{22} = 2^{11 \times 2} = (2^{11})^2 \\
&\equiv& (2^5)^2 = 2^{10} = 1024
\end{eqnarray}
よって、求める余りは \( 1024 \cdots \) （答）
