【数学A】例題4.1.13：合同式の利用1（One More）★★★

% 例題A4.1.13：合同式の利用1 （One More）★★★
(1)$3^{80}$を5で割ったときの余りを求めよ. (2)$200^{200}$を12で割ったときの余りを求めよ. (3)$123^{123}$の一の位の数を求めよ.

% 解答（例題A4.1.13）
(1)$3^1 \equiv 3\pmod 5,3^2 \equiv 9 \equiv 4\pmod 5,3^4 \equiv 4^2 \equiv 1\pmod 5$より,$$3^{80} \equiv\left(3^4\right)^{20} \equiv 1^{20} \equiv 1\pmod 5$$よって,$3^{80}$を5で割ったときの余りは,1 (2)$200 \equiv 8\pmod{12}$より,$200^{200} \equiv 8^{200}\pmod{12}$ここで,$8^2 \equiv 64 \equiv 4\pmod{12},8^3 \equiv 4 \cdot 8 \equiv 8\pmod{12},8^4 \equiv 8^2 \equiv 4\pmod{12}$より,$k$を自然数とすると,$$8^{2k} \equiv 4\pmod{12}$$したがって,$200^{200} \equiv 8^{200} \equiv 4\pmod{12}$よって,$200^{200}$を12で割ったときの余りは,4 (3) \begin{center}$123 \equiv 3\pmod{10},123^2 \equiv 3^2 \equiv 9\pmod{10},$$123^3 \equiv 3^3 \equiv 7\pmod{10}, 123^4 \equiv 3^4 \equiv 1\pmod{10}$\end{center} であるから,$$123^{123} \equiv\left(123^{4}\right)^{30} \cdot 123^3 \equiv 1^{30} \cdot 7 \equiv 7\pmod{10}$$よって,$123^{123}$の一の位の数は,7

% 問題A4.1.13
(1)$2^{50}$を7で割ったときの余りを求めよ. (2)$1000^{100}$を14で割ったときの余りを求めよ. (3)$456^{456}$の一の位の数を求めよ.

% 解答A4.1.13
(1)$2^1 \equiv 2\pmod 7,2^2 \equiv 4\pmod 7,2^3 \equiv 8 \equiv 1\pmod 7$より,$$2^{50} \equiv\left(2^3\right)^{16} \cdot 2^2 \equiv 1^{16} \cdot 4 \equiv 4\pmod 7$$よって,$2^{50}$を7で割ったときの余りは,4 (2)$1000 \equiv 6\pmod{14}$より,$1000^{100} \equiv 6^{100}\pmod{14}$ここで,$6^2 \equiv 36 \equiv 8\pmod{14},6^3 \equiv 8 \cdot 6 \equiv 6\pmod{14},6^4 \equiv 6^2 \equiv 8\pmod{14}$より,$k$を自然数とすると,$$6^{2k} \equiv 8\pmod{14}$$したがって,$1000^{100} \equiv 6^{100} \equiv 8\pmod{14}$よって,$1000^{100}$を14で割ったときの余りは,8 (3)$456 \equiv 6\pmod{10},456^2 \equiv 6^2 \equiv 6\pmod{10},456^3 \equiv 6^3 \equiv 6\pmod{10}$より,$k$を自然数とすると,$$456^{k} \equiv 6\pmod{10}$$よって,$456^{456}$の一の位の数は,6