(i) $11^{20}$ を100で割ったときの余りを求める。 (ii) $29^{13}$ を900で割ったときの余りを求める。

1. 問題の内容

(i) $11^{20}$ を100で割ったときの余りを求める。

(ii) $29^{13}$ を900で割ったときの余りを求める。

2. 解き方の手順

(i) $11^{20}$ を100で割ったときの余り

$11^2 = 121 \equiv 21 \pmod{100}$

$11^4 \equiv 21^2 = 441 \equiv 41 \pmod{100}$

$11^8 \equiv 41^2 = 1681 \equiv 81 \pmod{100}$

$11^{16} \equiv 81^2 = 6561 \equiv 61 \pmod{100}$

$11^{20} = 11^{16} \cdot 11^4 \equiv 61 \cdot 41 = 2501 \equiv 1 \pmod{100}$

(ii) $29^{13}$ を900で割ったときの余り

$29^2 = 841 \equiv 841 \pmod{900}$

$29^2 \equiv -59 \pmod{900}$

$29^3 \equiv 29 \cdot (-59) = -1711 \equiv -1711 + 1800 \equiv 89 \pmod{900}$

$29^4 \equiv (-59)^2 = 3481 \equiv 3481 - 3600 \equiv -119 \pmod{900}$

$29^5 \equiv 29 \cdot (-119) = -3451 \equiv -3451 + 3600 \equiv 149 \pmod{900}$

$29^6 \equiv (-59)^3 = -205379 \equiv -205379 + 229 \cdot 900 = -205379 + 206100 = 721 \equiv -179 \pmod{900}$

$29^{12} \equiv (-179)^2 = 32041 \equiv 32041 - 35 \cdot 900 = 32041 - 31500 = 541 \pmod{900}$

$29^{13} = 29^{12} \cdot 29 \equiv 541 \cdot 29 = 15689 \equiv 15689 - 17 \cdot 900 = 15689 - 15300 = 389 \pmod{900}$

3. 最終的な答え

(i) 1

(ii) 389