$5^{100}$ を36で割ったときの余りを求める問題です。

1. 問題の内容

$5^{100}$ を36で割ったときの余りを求める問題です。

2. 解き方の手順

まず、$5^2 = 25$ であることに注目します。

$25 = 36 - 11$ なので、$5^2$ を36で割った余りは $-11$ 、つまり25となります。

また、$5^3 = 125$ であり、$125 = 36 \times 3 + 17$ より $5^3$ を36で割った余りは17となります。

もう少し工夫してみます。

$5^2 = 25 \equiv -11 \pmod{36}$ です。

$5^3 = 125 \equiv 17 \pmod{36}$ です。

$5^4 = (5^2)^2 \equiv (-11)^2 = 121 \equiv 13 \pmod{36}$ です。

$5^5 = 5 \times 5^4 \equiv 5 \times 13 = 65 \equiv 29 \pmod{36}$ です。

別の方法として、$36 = 4 \times 9$ であることに着目します。

$5^{100} \pmod{4}$ について、$5 \equiv 1 \pmod{4}$ より $5^{100} \equiv 1^{100} \equiv 1 \pmod{4}$ です。

$5^{100} \pmod{9}$ について、オイラーの定理より、$a^{\phi(n)} \equiv 1 \pmod{n}$ （$a$ と $n$ は互いに素）です。

$\phi(9) = 9 \times (1 - \frac{1}{3}) = 9 \times \frac{2}{3} = 6$ なので、$5^6 \equiv 1 \pmod{9}$ です。

したがって、$5^{100} = 5^{6 \times 16 + 4} = (5^6)^{16} \times 5^4 \equiv 1^{16} \times 5^4 \equiv 5^4 \pmod{9}$ です。

$5^2 = 25 \equiv 7 \pmod{9}$ なので、$5^4 \equiv 7^2 = 49 \equiv 4 \pmod{9}$ です。

$5^{100} \equiv 1 \pmod{4}$ かつ $5^{100} \equiv 4 \pmod{9}$ です。

$5^{100} = 9k + 4 \equiv 1 \pmod{4}$ となる $k$ を求めます。

$9k + 4 \equiv k \equiv 1 \pmod{4}$ より $k = 4m + 1$ です。

したがって、$5^{100} = 9(4m + 1) + 4 = 36m + 9 + 4 = 36m + 13$ となります。

よって、$5^{100} \equiv 13 \pmod{36}$ です。

3. 最終的な答え

13