問題#B009 ★☆☆☆
（１）$3^{100}$を$4$で割ったときの余りを求めよ。
（２）$3^{100}$を$5$で割ったときの余りを求めよ。
（３）$3^{100}$を$6$で割ったときの余りを求めよ。
《ポイント》
合同式の威力を体感するには丁度良い問題です。合同式の定義と性質を簡単に復習します。
整数$a、b$を正の整数$n$で割ったときの余りが等しいとき、「$a$と$b$は$n$を法として合同である」といい、これを
「$a \equiv b \pmod{n}$」
と表すのが合同式の定義でした。$a \equiv b \pmod{n}, c \equiv d \pmod{n}$であれば、合同式において以下の関係が成立します。
（１） $a+c \equiv b+d \pmod{n}$
（２） $a-c \equiv b-d \pmod{n}$
（３） $ac \equiv bd \pmod{n}$
（４） $a^k \equiv b^k \pmod{n}$ （$k$は任意の自然数）
ここでは本問を合同式で解答してみます。合同式についての詳しい内容は「整数第２章第３節」を参照してください。
《解答例》
（１）
$3 \equiv -1 \pmod{4}$であるから、$$\begin{align} 3^{100} & \equiv (-1)^{100} \pmod{4} \\ &=1 \end{align}$$となる。故に$3^{100}$を$4$で割ったときの余りは $1$ である。
（答）$1$
（２）
$3^2=9 \equiv -1 \pmod{5}$であるから、$$\begin{align} 3^{100} & = (3^2)^{50} \\ & \equiv (-1)^{50} \pmod{5} \\ &=1 \end{align}$$となる。故に$3^{100}$を$5$で割ったときの余りは $1$ である。
（答）$1$
（３）
$6=2 \cdot 3$より、$3^{100}$を$2$で割ったときの余りと$3$で割ったときの余りを別々に考える。
$3 \equiv 1 \pmod{2}$であるから、$$\begin{align} 3^{100} & \equiv 1^{100} \pmod{2} \\ &=1 \end{align}$$となる。故に$3^{100}$を$2$で割ったときの余りは $1$ である。
また、$3^{100}$は$3$の倍数であるから、$3^{100}$を$3$で割ったときの余りは $0$ である。
$2$で割って$1$余り、$3$で割り切れるような整数は$6m+3 \ (m \in \mathbb{Z})$と表せるから、$3^{100}$を$6$で割ったときの余りは $3$ である。
（答）$3$
《コメント》
$3^{100}$は
515377520732011331036461129765621272702107522001
という$48$桁の数です。この値を手計算で求めるのはかなり厳しいですが、合同式を使えば指数計算はほとんど不要になります。合同式を知っているといないとでは対応できる問題の幅にかなり差が付いてしまうので、特に難関大を狙っている人なら必ず身に付けておかねばなりません。