おいしい数学HOMEへのリンク

合同式

整数(入試の標準) ★★


アイキャッチ

合同式を扱います.

合同式が初めての人向けで,わかりやすいこと,使いこなせることを優先しました.



合同式とは

ポイント

合同式

$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 \equiv b \ (\hspace{-2mm}\mod m)$ と表す.

これが定義ですが,この説明だと初学者にはわかりにくいので,上の説明をとりました.

$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$ は自然数です.累乗は乗法から言えますね.割り算だけはできないので注意です.


証明は教科書や参考書に譲ります.合同式同士の足し算,引き算,かけ算は等式と同じように自由にできます.

例題と練習問題

例題

例題

(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)$

として言葉で説明してもいいですね.