【数学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の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(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(3^4)^{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)

$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}$

であるから，

\[
123^{123}\equiv(123^{4})^{30}\cdot 123^3\equiv 1^{30}\cdot 7\equiv 7\pmod{10}
\]

よって，$123^{123}$の一の位の数は，7

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.1.13：合同式の利用1（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) $2^{50}$を7で割ったときの余りを求めよ．

(2) $1000^{100}$を14で割ったときの余りを求めよ．

(3) $456^{456}$の一の位の数を求めよ．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.1.13の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) $2^1\equiv 2\pmod 7,2^2\equiv 4\pmod 7,2^3\equiv 8\equiv 1\pmod 7$より，

\[
2^{50}\equiv(2^3)^{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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.13の側注：合同式の利用1（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
$3^4\equiv 1\pmod{5}$より，$(3^4)^n\equiv 1\pmod{5}$

% 側注2
$80=4\cdot 20$

% 側注3
$8^5\equiv 8\pmod{12},8^6\equiv 4\pmod{12},\ldots$と余りは4と8が繰り返される．

% 側注4
$8^{2k}$において，$k=100$のとき，$8^{2\cdot 100}=8^{200}$

% 側注5
一の位の数は，10で割ったときの余りと等しいことから，$\pmod{10}$を考える．

% 側注6
$123=4\cdot 30+3$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.1.13の側注：合同式の利用1（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
$2^3\equiv 1$より，$(2^3)^n\equiv 1\pmod{7}$

% 側注2
$50=3\cdot 16+2$

% 側注3
$6^5\equiv 6\pmod{14},6^6\equiv 8\pmod{14},\ldots$と余りは6と8が繰り返される．

% 側注4
$6^{2k}$において，$k=50$のとき，$6^{2\cdot 50}=6^{100}$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.13の考え方・補足など：合同式の利用1（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$a\equiv b\pmod{m}$のとき，$a^n\equiv b^n\pmod{m}$が成り立つことを利用する（合同式の性質）．また，合同式を用いた余りに関する問題は，周期性を上手く考えると計算が楽になることが多い．

(1) $3^n\pmod{5}$を考えると，$3^n\equiv 1\pmod{5}$となる$n$が見つかるので，それを利用する．

(2) $a^n$の$a$を指数の底という．先に，合同式を利用して指数の底を扱いやすい数（小さい数）にしてから，余りの周期性を考えると計算が楽になる．

(3) ある自然数$N$の一の位の数は，$N$を10で割った余りと等しいので，$\pmod{10}$を考える．