% 例題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）
(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
(1)$n$を整数とする.$n^2$を7で割った余りをすべて求めよ. (2)$n$を自然数とする.合同式を用いて,$7^n+2 \cdot 5^{2n}$は3の倍数であることを証明せよ.
% 解答A4.1.14
(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$
