合同式
整数(入試の標準) ★★
合同式を扱います．
合同式とは
合同式
$a$，$b$ を整数，$m$ を自然数とする．
$a$ を $m$ で割ったときの余りが $b$ のとき，( $a$ や $b$ は $m$ より大きくても小さくてもいいし，負の数でも構わない．)
$\boldsymbol{a \equiv b \ (\hspace{-2mm}\mod m)}$
と表す．
※ $a$ 合同 $b$ モッド $m$，$m$ を法として $a$ と $b$ は合同，と言ったりします．
上は初めての方向けの説明で，きちんとした定義が以下です．
合同式の定義
$a$，$b$ を整数，$m$ を自然数とする．$a-b$ が $m$ の倍数であるとき，$a$，$b$ は $m$ を法として合同であるといい
$\boldsymbol{a \equiv b \ (\hspace{-2mm}\mod m)}$
と表す．すなわち
$\boldsymbol{a \equiv b \ (\hspace{-2mm}\mod m) \Longleftrightarrow \ a-b=km \ (k \in \mathbb{Z})}$
例
$100$ を $7$ で割ると $14$ 余り $2$ なので
$100\equiv 2$ $(\hspace{-2mm}\mod 7$ )
となります．しかし，$100$ を $7$ で割ると $13$ 余り $9$ と書けなくもないですよね？つまり
$100\equiv 9$ $(\hspace{-2mm}\mod 7$ )
と書いても正しいです．合同式としては余りが割る数より大きくてもかまいません．なんなら $100$ を $7$ で割ると $15$ 余り $-5$ とも書けるので
$100\equiv -5$ $(\hspace{-2mm}\mod 7$ )
でもOKです．つまり合同式として正しい式は無限に書けます．
例
$-13$ を $17$ で割ると $-1$ 余り $4$ なので
$-13\equiv 4$ $(\hspace{-2mm}\mod 17$ )
と書けます．$a$ や商がマイナスでも構いません．
合同式の性質
合同式の性質
$a \equiv b$ $(\hspace{-2mm}\mod m$ )，$c \equiv d$ $(\hspace{-2mm}\mod m$ )のとき以下のように加減乗が成り立つ．
加法 $a+c \equiv b+d$ $(\hspace{-2mm}\mod m$ )
減法 $a-c \equiv b-d$ $(\hspace{-2mm}\mod m$ )
乗法 $ac \equiv bd$ $(\hspace{-2mm}\mod m$ )
累乗 $a^{n} \equiv b^{n}$ $(\hspace{-2mm}\mod m$ )
$n$ は自然数です．累乗は乗法から言えますね．割り算だけは無条件にはできないので注意です．
以下 $m$ を法とする合同式とする．
$a-b=km$，$c-d=lm$ $(k,l \in \mathbb{Z})$ とおく．
加法の証明
$a+c-(b+d)=(k+l)m$
$\Longleftrightarrow \ a+c \equiv b+d$
減法の証明
$a-c-(b-d)=(k-l)m$
$\Longleftrightarrow \ a-c \equiv b-d$
乗法の証明
$ac-bd=(b+km)(d+lm)-bd=(bl+dk+klm)m$
$\Longleftrightarrow \ ac \equiv bd$
合同式同士の足し算，引き算，かけ算は等式と同じように自由にできます．
一方で割り算はできないと考えていた方が無難なぐらいですが，以下の条件に限って割り算ができます．
合同式の性質(除法)
$m$ と $c$ が互いに素ならば次が成り立つ．
$ac \equiv bc$ $(\hspace{-2mm} \mod m)$ $\Longleftrightarrow$ $a \equiv b$ $(\hspace{-2mm} \mod m)$
$\Longleftarrow$ の証明
上の乗法の性質より明らかです．
$\Longrightarrow$ の証明
$ac \equiv bc$ $(\hspace{-2mm} \mod m)$ のとき，$ac-bc=km$ $(k \in \mathbb{Z})$ とおく．
$c(a-b)=km$
これより $km$ は $c$ の倍数だが，$m$ と $c$ が互いに素より，$k$ が $c$ の倍数なので $k=k'c$ $(k' \in \mathbb{Z})$ とおくと
$c(a-b)=k’cm$
$a-b=k'm$
$\therefore \ a \equiv b$ $(\hspace{-2mm} \mod m)$
例題と練習問題
例題
例題
(1) $50^{5}$ を $7$ で割った余りを求めよ．
(2) $7^{50}$ を $25$ で割った余りを求めよ．
(3) $2^{80}$ を $7$ で割った余りを求めよ．
(4) $n$ を $7$ で割った余りが $3$ のとき，$n^{3}+2n+1$ を $7$ で割った余りを求めよ．
解答
(1) $50\equiv1$ $(\hspace{-2mm}\mod 7$ )より，両辺5乗すると
$50^{5}\equiv1^{5}\equiv1$ $(\hspace{-2mm}\mod 7$ )
よって余り $\boldsymbol{1}$
(2) $7^{50}=49^{25}\equiv(-1)^{25}\equiv-1\equiv24$ $(\hspace{-2mm}\mod 25$ )
よって余り $\boldsymbol{24}$
※ 余りが $1$ か $-1$ になるように累乗を探すといいですね．
(3) $2^{80}=2^{3\cdot26+2}=4\cdot8^{26}\equiv4\cdot1^{26}\equiv4$ $(\hspace{-2mm}\mod 7$ )
よって余り $\boldsymbol{4}$
※ $8\equiv1$ $(\hspace{-2mm}\mod 7$ )なんで，合同式としては $8$ と $1$ は同じだくらいの感覚でOKです．
(4) $n\equiv3$ $(\hspace{-2mm}\mod 7$ )より
$n^{3}+2n+1\equiv 3^{3}+2\cdot3+1\equiv34\equiv6$ $(\hspace{-2mm}\mod 7$ )
よって余り $\boldsymbol{6}$
※ $n$ と $3$ が合同です．普通の等式の変形と同じように代入していき，最後は答えとして適切な余りを選びます．$n=7k+3$ などと代入して展開して解くと大変ですね．
以上のように，合同式を用いると筆記が楽になり，計算もミスなく速く解けることが多いです．
練習問題
練習
(1) $3^{100}$ を $8$ で割った余りを求めよ．
(2) $2^{300}$ を $9$ で割った余りを求めよ．
(3) $2^{111}$ を $15$ で割った余りを求めよ．
(4) $17^{111}$ の一の位の数を求めよ．
(5) $n$ を自然数とする．$1000^{n}+(-1)^{n-1}$ が $7$ の倍数であることを証明せよ．
(6) $n$ を $5$ で割った余りが $4$ のとき，$n^{3}-3n^{2}+3n-1$ を $5$ で割った余りを求めよ．
(7) $n$ を $2$ 以上の自然数とするとき，$n^{5}-n$ が $30$ の倍数になることを示せ．
解答
(1)
$3^{100}=9^{50}\equiv1^{50}\equiv1$ $(\hspace{-2mm}\mod 8$ )
よって余り $\boldsymbol{1}$
(2)
$2^{300}=8^{100}\equiv(-1)^{100}\equiv1$ $(\hspace{-2mm}\mod 9$ )
よって余り $\boldsymbol{1}$
(3)
$2^{111}=2^{4\cdot27+3}=8\cdot16^{27}\equiv8\cdot1^{27}\equiv8$ $(\hspace{-2mm}\mod 15$ )
よって余り $\boldsymbol{8}$
(4)
$17^{111}$
$\equiv7^{111}\equiv7^{2\cdot55+1}\equiv7\cdot49^{55}\equiv7\cdot(-1)^{55}\equiv-7\equiv3$ $(\hspace{-2mm}\mod 10$ )
よって一の位は $\boldsymbol{3}$
(5)
$1000^{n}+(-1)^{n-1}$
$\equiv (-1)^{n}-(-1)^{n}\equiv 0$ $(\hspace{-2mm}\mod 7$ )
※ 実は $11$ の倍数，$13$ の倍数でもあります．7，11，13の倍数の判定法にこの等式を使います．
(6) $n\equiv4$ $(\hspace{-2mm}\mod 5$ )より
$n^{3}-3n^{2}+3n-1=(n-1)^{3}\equiv(4-1)^{3}\equiv27\equiv2$ $(\hspace{-2mm}\mod 5$ )
よって余り $\boldsymbol{2}$
(7)
$n^{5}-n=n(n^{2}-1)(n^{2}+1)=(n-1)n(n+1)(n^{2}+1)$
より，連続する3つの自然数の積は $2$ の倍数かつ $3$ の倍数なので $6$ の倍数であるから，後は $n^{5}-n$ が $5$ の倍数であることを示す．
(ⅰ) $n\equiv0$ $(\hspace{-2mm}\mod 5$ )のとき
$n^{5}-n\equiv0^{5}-0\equiv0$ $(\hspace{-2mm}\mod 5$ )
(ⅱ) $n\equiv1$ $(\hspace{-2mm}\mod 5$ )のとき
$n^{5}-n\equiv1^{5}-1\equiv0$ $(\hspace{-2mm}\mod 5$ )
(ⅲ) $n\equiv2$ $(\hspace{-2mm}\mod 5$ )のとき
$n^{5}-n\equiv2^{5}-2\equiv30\equiv0$ $(\hspace{-2mm}\mod 5$ )
(ⅳ) $n\equiv3$ $(\hspace{-2mm}\mod 5$ )のとき
$n^{5}-n\equiv3^{5}-3\equiv240\equiv0$ $(\hspace{-2mm}\mod 5$ )
(ⅴ) $n\equiv4$ $(\hspace{-2mm}\mod 5$ )のとき
$n^{5}-n\equiv4^{5}-4\equiv1020\equiv0$ $(\hspace{-2mm}\mod 5$ )
以上より，$n^{5}-n$ は $5$ の倍数である．
よって $n^{5}-n$ は $30$ の倍数．
※ 場合分けを $n\equiv0$，$n\equiv\pm1$，$n\equiv\pm2$ $(\hspace{-2mm}\mod 5$ )としてもいいですし，合同式使いませんが
$n^{5}-n$
$=(n-1)n(n+1)(n^{2}+1)$
$=(n-1)n(n+1)\{(n-2)(n+2)+5\}$)
$=(n-2)(n-1)n(n+1)(n+2)+5(n-1)n(n+1)$
として言葉で説明してもいいですね．