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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.14：合同式の利用2（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) $n$を整数とする．合同式を用いて，$n^2+1$は3の倍数ではないことを証明せよ．

(2) $n$を自然数とする．合同式を用いて，$19^n+2^4\cdot(-32)^{n}$は17の倍数であることを証明せよ．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.14の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) すべての整数$n$について，

\[
n\equiv 0\pmod 3,n\equiv 1\pmod 3,n\equiv 2\pmod 3
\]

のいずれかである．

(i) $n\equiv 0\pmod 3$のとき，$n^2+1\equiv 0^2+1\equiv 1\pmod 3$

(ii) $n\equiv 1\pmod 3$のとき，$n^2+1\equiv 1^2+1\equiv 2\pmod 3$

(iii) $n\equiv 2\pmod 3$のとき，$n^2+1\equiv 2^2+1\equiv 5\equiv 2\pmod 3$

よって，(i)〜(iii)より，$n^2+1$は3の倍数ではない．$\blacksquare$

(2) $19=17+2$より，$19\equiv 2\pmod{17}$であるから，

\[
19^n\equiv 2^n\pmod{17}
\]

$-32=-2\cdot 17+2$より，$-32\equiv 2\pmod{17}$であるから，

\[
(-32)^{n}\equiv 2^{n}\pmod{17}
\]

したがって，

\[
19^n+2^4\cdot(-32)^{n}\equiv 2^n+16\cdot 2^{n}=17\cdot 2^n\equiv 0\pmod{17}
\]

よって，$19^n+2^4\cdot(-32)^{n}$は17の倍数である．$\blacksquare$

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

(1) $n$を整数とする．$n^2$を7で割った余りをすべて求めよ．

(2) $n$を自然数とする．合同式を用いて，$7^n+2\cdot 5^{2n}$は3の倍数であることを証明せよ．

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

(1) すべての整数$n$について

\[
n\equiv 0\pmod 7,n\equiv 1\pmod 7,n\equiv 2\pmod 7,n\equiv 3\pmod 7,
\]

\[
n\equiv 4\pmod 7,n\equiv 5\pmod 7,n\equiv 6\pmod 7
\]

のいずれかである．

(i) $n\equiv 0\pmod 7$のとき，$n^2\equiv 0^2\equiv 0\pmod 7$

(ii) $n\equiv 1\pmod 7$のとき，$n^2\equiv 1^2\equiv 1\pmod 7$

(iii) $n\equiv 2\pmod 7$のとき，$n^2\equiv 2^2\equiv 4\pmod 7$

(iv) $n\equiv 3\pmod 7$のとき，$n^2\equiv 3^2\equiv 9\equiv 2\pmod 7$

(v) $n\equiv 4\pmod 7$のとき，$n^2\equiv 4^2\equiv 16\equiv 2\pmod 7$

(vi) $n\equiv 5\pmod 7$のとき，$n^2\equiv 5^2\equiv 25\equiv 4\pmod 7$

(vii) $n\equiv 6\pmod 7$のとき，$n^2\equiv 6^2\equiv 36\equiv 1\pmod 7$

よって，(i)〜(vii)より，$n^2$を7で割った余りは$0,1,2,4$のいずれかである．

(2) $7=6+1$より，$7\equiv 1\pmod{3}$であるから，

\[
7^n\equiv 1^n\equiv 1\pmod{3}
\]

$5=3+2$より，$5\equiv 2\pmod{3}$であるから，

\[
5^{2n}\equiv(2)^{2n}\equiv 4^n\equiv 1^n\equiv 1\pmod{3}
\]

したがって，

\[
7^n+2\cdot 5^{2n}\equiv 1+2\cdot 1\equiv 3\equiv 0\pmod{3}
\]

よって，$7^n+2\cdot 5^{2n}$は3の倍数である．$\blacksquare$

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

% 側注1
(i)〜(iii)のいずれの場合も，$n^2+1\equiv 0\pmod 3$とはならない．

% 側注2
$a\equiv b\pmod{m}$のとき，
\[
a^n\equiv b^n\pmod{m}
\]

% 側注3
指数の底を$2^n$に合わせる．

% 側注4
$a\equiv b\pmod m,c\equiv d\pmod m$のとき，
\[
a+c\equiv b+d\pmod m
\]

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

% 側注1
$a\equiv b\pmod{m}$のとき，
\[
a^n\equiv b^n\pmod{m}
\]

% 側注2
$a\equiv b\pmod m,c\equiv d\pmod m$のとき，
\[
a+c\equiv b+d\pmod m
\]

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

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

(1) 整数を$3k,3k+1,3k+2(k\text{は整数})$と分けることでも証明できるが，問題文に「合同式を用いて」とあるので，ここでは合同式を利用した証明を考える．

(2) 17で割ることを考え，合同式を用いて指数の底を$2^n$の形に合わせる．