割り算の余りの性質と合同式

こんにちは、リンス(@Lins016)です。
今回は割り算の余りの性質と合同式について学習していこう。

合同式を理解する

合同式って教科書では、発展や研究に載ってるから授業できちんと取り扱わない学校も結構多いと思うんだ。

確かに発展や研究だからセンター試験には出題されないだろうし、授業で取り扱わなくても問題ないって言えば問題ないんだろうけど、難関大学の入試問題だと普通に出題されるから、受験を考えてる人は知っておかないといけないよ。

今回はこの合同式の基本的な性質を理解しよう。

割り算の余りの性質

整数をある数で割って余りで分類する方法は前に学習したよね。まずは復習しておこう。

今回はそれをさらに発展させていこう。
例えば\(\small{ \ 2 \ }\)つの整数\(\small{ \ a, \ b \ }\)を\(\small{ \ 7 \ }\)で割った余りが\(\small{ \ 2, \ 3 \ }\)だったとすると、\(\small{ \ a=7k+2, \ b=7l+3 \ }\)（\(\small{ \ k, \ l \ }\)は整数）って表すことができるよね。
この\(\small{ \ 2 \ }\)つの整数\(\small{ \ a, \ b \ }\)の和と積を\(\small{ \ 7 \ }\)で割った余りを考えてみよう。

整数\(\small{ \ a, \ b \ }\)の和は
\(\small{\begin{eqnarray} \ a+b&=&7k+2+7l+3\\
&=&7(k+l)+5 \ \end{eqnarray}}\)
ってなるから\(\small{ \ 7 \ }\)で割った余りは\(\small{ \ 5 \ }\)になるよね。

整数\(\small{ \ a, \ b \ }\)の積は
\(\small{\begin{eqnarray} \ ab&=&(7k+2)(7l+3)\\
&=&49kl+7k+7l+6\\
&=&7(7kl+k+l)+6 \ \end{eqnarray}}\)
ってなるから\(\small{ \ 7 \ }\)で割った余りは\(\small{ \ 6 \ }\)になるよね。

このことから整数\(\small{ \ a, \ b \ }\)の和や積を\(\small{ \ 7 \ }\)で割った余りは、整数\(\small{ \ a, \ b \ }\)を\(\small{ \ 7 \ }\)で割った余りの和や積を\(\small{ \ 7 \ }\)で割った余りと同じになるってことなんだ。

このことから一般的に次のことが言えるから覚えておこう。
\(\small{ \ m \ }\)を正の整数として、\(\small{ \ 2 \ }\)つの整数\(\small{ \ a, \ b \ }\)を\(\small{ \ m \ }\)で割った余りを\(\small{ \ r, \ r' \ }\)とすると
①\(\small{ \ a+b \ }\)を\(\small{ \ m \ }\)で割った余りは、\(\small{ \ r+r' \ }\)を\(\small{ \ m \ }\)で割った余りに等しい
②\(\small{ \ a-b \ }\)を\(\small{ \ m \ }\)で割った余りは、\(\small{ \ r-r' \ }\)を\(\small{ \ m \ }\)で割った余りに等しい
③\(\small{ \ ab \ }\)を\(\small{ \ m \ }\)で割った余りは、\(\small{ \ rr' \ }\)を\(\small{ \ m \ }\)で割った余りに等しい
④\(\small{ \ a^k \ }\)を\(\small{ \ m \ }\)で割った余りは、\(\small{ \ r^k \ }\)を\(\small{ \ m \ }\)で割った余りに等しい

余りで分類することに加えて、この性質もすごく重要なことだから覚えておこう。

④の\(\small{ \ a^k \ }\)は③を\(\small{ \ a, \ b \ }\)を\(\small{ \ a, \ a \ }\)って考えると\(\small{ \ r^2 \ }\)を割った余りに等しいってことになるよね。これを繰り返していくことで④が言えるんだ。

\(\small{ \ a=mp+r \ }\)とすると\(\small{ \ a^k \ }\)は二項定理を使うと

\(\small{\begin{eqnarray} \ a^k&=&(mp+r)^k\\
&=&_k\mathrm{C}_{0}(mp)^k+_k\mathrm{C}_{1}(mp)^{k-1}r+_k\mathrm{C}_{2}(mp)^{k-2}r^2+ \cdots+_k\mathrm{C}_{k-1}(mp)r^{k-1}+_k\mathrm{C}_{k}r^k \ \end{eqnarray}}\)

になるよね。

このとき\(\small{ \ _k\mathrm{C}_{k}r^k \ }\)の項以外は\(\small{ \ m \ }\)が入っているから\(\small{ \ a^k \ }\)を\(\small{ \ m \ }\)で割った余りは\(\small{ \ _k\mathrm{C}_{k}r^k \ }\)つまり\(\small{ \ r^k \ }\)を\(\small{ \ m \ }\)で割った余りになるんだ。

合同式とは

\(\small{ \ 2 \ }\)つの整数\(\small{ \ a, \ b \ }\)を\(\small{ \ m \ }\)で割った余りがどちらも\(\small{ \ r \ }\)だったとすると、\(\small{ \ a=mp+r, \ b=mq+r \ }\)（\(\small{ \ p, \ q \ }\)は整数）って表すことができるよね。

このとき\(\small{ \ a-b=m(p-q) \ }\)になるから\(\small{ \ a-b \ }\)は\(\small{ \ m \ }\)の倍数って言えるよね。

この\(\small{ \ a, \ b \ }\)を\(\small{ \ m \ }\)で割った余りが等しいとき、「\(\small{ \ a \ }\)と\(\small{ \ b \ }\)は\(\small{ \ m \ }\)を法として合同である」って言うんだ。

これを記号で書くと
\(\small{ \ a \equiv b \pmod m \ }\)って表して、この式を合同式っていうんだ。

「\(\small{ \ m \ }\)を法として合同」って言われてもピンとこないかもしれないけど、「\(\small{ \ m \ }\)で割った余りが等しい」って言ってるのと同じことだからね。
つまり合同式っていうのは余りに注目した式とも言えるってことなんだ。

合同式の性質

それじゃ次に合同式の性質を考えてみよう。

\(\small{ \ a \equiv c \pmod m\cdots(1) \ }\)、\(\small{ \ b \equiv d \pmod m\cdots(2) \ }\)のとき
①\(\small{ \ a+b \equiv c+d \pmod m \ }\)
②\(\small{ \ a-b \equiv c-d \pmod m \ }\)
③\(\small{ \ ab \equiv cd \pmod m \ }\)
④\(\small{ \ a^k \equiv c^k \pmod m \ }\)
を満たすんだ。

これは\(\small{ \ 2 \ }\)つの合同式\(\small{ \ (1)(2) \ }\)を加えた①、\(\small{ \ (1)(2) \ }\)を引いた②、\(\small{ \ (1)(2) \ }\)の積の③のそれぞれの式が成り立つってこと。

④のべき乗の式は特によく利用する式だから確実に覚えておこう。③の\(\small{ \ (1)(2) \ }\)の積を\(\small{ \ (1)(1) \ }\)の積として繰り返した式になるよね。

次に合同式の書き方について考えていこう。
\(\small{ \ 23 \ }\)を\(\small{ \ 10 \ }\)で割った割った余りを合同式を利用して書くと
\(\small{ \ 23 \equiv 3 \pmod {10} \ }\)ってかけるよね。

実はこれってこうも書けるんだ。
\(\small{ \ 23 \equiv 13\equiv 3 \pmod {10} \ }\)

これは「\(\small{ \ 23 \ }\)を\(\small{ \ 10 \ }\)で割った余り」と「\(\small{ \ 13 \ }\)を\(\small{ \ 10 \ }\)で割った余り」と「\(\small{ \ 3 \ }\)を\(\small{ \ 10 \ }\)で割った余り」は等しいってことを書いた式で、合同の記号（\(\small{ \ \equiv \ }\)）で式をつなげて書くことが出来るんだ。

ちなみに\(\small{ \ 10 \ }\)で割った余りを考えるとき元の数（この場合\(\small{ \ 23 \ }\)）に\(\small{ \ 10 \ }\)の倍数を足したり引いたりした数の余りは全て一緒だから\(\small{ \ 53\equiv 43\equiv23 \equiv 13\equiv 3 \pmod {10} \ }\)とも書けるから覚えておこう。

次に\(\small{ \ 23^4 \ }\)を\(\small{ \ 10 \ }\)で割った余りを調べてみよう。
\(\small{ \ 23 \equiv 3 \pmod {10} \ }\)より
\(\small{ \ 23^4 \equiv 3^4 \equiv 9^2\equiv (-1)^2 \equiv 1 \pmod {10} \ }\)
ってなるから、余りは\(\small{ \ 1 \ }\)って簡単に調べることができるんだ。

この計算のポイントは、\(\small{ \ 23 \ }\)を\(\small{ \ 3 \ }\)に変更したように、なるべく小さい数に変更することと、\(\small{ \ 9 \ }\)を\(\small{ \ -1 \ }\)に変更したように指数の計算の場合できるだけ\(\small{ \ 1 \ }\)を作って計算するってことを覚えておこう。
そうすることで簡単に計算できるからね。

とにかく\(\small{ \ 9 \equiv 1 \pmod 8 \ }\)や\(\small{ \ 2^3 \equiv 1 \pmod 7 \ }\)みたいに割った余りが\(\small{ \ 1 \ }\)になる数を見つけよう。そうすることで簡単に計算することが出来るからね。

Point 割り算の余りの性質と合同式

①割り算の余りの性質と計算方法を理解する
②合同式の性質と計算方法を理解する

今回は合同式を使って証明したけど、すでに数列を勉強した受験生は数学的帰納法でも証明できないとダメだよ。忘れている人は復習しておこう。