家庭教師の想い 
合同式の習得は必須ではありませんが、大学の入試では合同式を知っておいた方が解きやすい問題がふつうに出題されています。果敢にチャレンジ精神を発揮して、合同式の習得にチャレンジしてみませんか？
ここではできるだけ具体例で、わかりやすく説明していきます。
目次
日常にある「合同」の例
時刻の表し方を考えてみてください。
例えば「午後１時」は「１３時」ともいえます。
また「深夜１時」を「２５時」というときもあります。
では、これら「１」と「１３」と「２５」の共通点は何でしょうか？
そうですね、１２で割ったときの余りがすべて同じで「１」になります。
このような整数どうしを合同というのです。
「合同式」というと、わたしたちの日常には全く関係ないように思うかも知れませんが、実はこれほど密接に関わっているものはないのです。
合同式って、どんな式？
数学の定義は正確に理解しなければなりません。それがすべての出発点だからです。出発点があやふやだとそれ以降すべてあやふやになる危険があります。
ちょっと難しいのですが定義をしっかり理解しておきましょう。
合同式の定義は次のとおりです。
$a$, $b$ は整数, $m$ は正の整数とする。
$a$ を $m$ で割ったときの余りと, $b$ を $m$ で割った余りが等しいとき, $a-b$ は $m$ の倍数である。このとき,
$a$ と $b$ は $m$ を法として合同であるという。
このことを
$$a \equiv b\pmod m$$
と表す。このような式を合同式という。
一読しただけではよく分かりませんね。では、この定義を式を立てて確認していきましょう。
$a$ を $m$ で割った商を $q_1$, 余りを $r_1$ , $b$ を $m$ で割った商を $q_2$, 余りを $r_2$ とします。$q_1$, $q_2$ は整数, $m, r_1$, $ r_2 $ は正の整数です。
すると次の式が成り立ちます。
$a \ = \ mq_1+r_1$ ••• ①
$b \ = \ mq_2+r_2$ ••• ②
①ー②を計算して整理すると
$a-b=m(q_1- q_2)+(r_1- r_2)$
となります。
ここで $r_1=r_2$ 、 すなわち余りが同じならば $r_1-r_2=0$ となり、また $(q_1-q_2)$は整数ですから、$a-b$ は $m$ の倍数、すなわち $a-b$ は $m$ で割り切れます。
これをさっきの時刻の例で言えば、「１」と「１３」から、１２で割った余りである「１」をそれぞれから引けば、そのふたつとも１２で割り切れるという意味です。そのとき「１」と「１３」は「１２」を法として合同といいます。
$$1 \equiv 13\pmod {12}$$
つまり、同じ正の数で割った余りが同じになる２つの整数は「合同」だというのです。
合同式の性質
さて定義によって「合同」および「合同式」が決まると、それによって自動的に成り立ついくつかの事実が現れます。それらを確認していきましょう。
以下では $a, b, c, d$ は整数, $m, k$ は正の整数とします。
$a \equiv a\pmod m$
この式の意味は「ふたつの数が同じなら、同じ数で割った余りも同じ」であることを示しています。これは当然だと納得できますね。
$a \equiv b\pmod m$ のとき $b \equiv a\pmod m$
合同式は交換法則が成り立っています。これも納得ですね。
$a \equiv b\pmod m$, $b \equiv c\pmod m$のとき, $a \equiv c\pmod m$
５を２で割ったときの余りが１、９を２で割った余りも１だから、５と９は法を２として合同です。
$5 \equiv 9\pmod 2$
また１５を２で割った余りも２なので、９と１５は合同です。
$9 \equiv 15\pmod 2$
だから５と１５も２を法として合同なのです。
$5 \equiv 15\pmod 2$
これは、３つの整数 $5, 9, 15$ をそれぞれ $2$ で割ったときの余りがすべて同じであることを表しています。
上記の３つの性質は納得しやすいものですね。これを基本にして次の計算法則が成り立ちます。
和の合同式
$a \equiv c\pmod m$, $b \equiv d\pmod m$ のとき$$a+b \equiv c+d \pmod m$$
この意味は、法が同じであるふたつの合同式は、辺々どうしを足しても構わないということです。
簡単な例で確認してみましょう。次の式が成り立っているのを確認してください。
$ 4\equiv 10\pmod 3$ ••• ①
$ 8\equiv 14\pmod 3$ ••• ②
$4$ を $3$ で割った余りと $10$ を $3$ で割った余りは、ともに「$1$」なので合同式①が成り立ちます。
また、$8$ を $3$ で割った余りと $14$ を $3$ で割った余りは、ともに「$2$」なので合同式②が成り立ちます。
ところで $4$ と $8$ を足すと $12$ ですが、$12$ を $3$ で割れば余りは「$0$」です。また$10$ と $14$ を足せば $24$ ですが、$24$ を $3$で割れば、やはり余りは「$0$」です。つまり余りが同じになります。
では①と②の合同式の辺どうしを和の公式どおりに足してみましょう。
$4+8 \equiv 10+14 \pmod 3$
$12 \equiv 24 \pmod 3$ ••• ③
③の式は $12$ を $3$ で割った余りは $24$ を $3$ で割った余りに等しいことを表しています。確かにそのようになっています。
厳密には、この式が一般的に成り立つ証明を理解する必要があります。しかしながら、それを見たからといって、必ずしも実感をもたらしてくれるとは限りません。
公式を使いこなすためには、証明が理解できなくても、このような具体例でもいいので自分で納得しておくべきです。
差の合同式
$a \equiv c\pmod m$, $b \equiv d\pmod m$ のとき$$a-b \equiv c-d \pmod m$$
これも具体例で確認しましょう。先程使った式を使います。
$ 4\equiv 10\pmod 3$ ••• ①
$ 8\equiv 14\pmod 3$ ••• ②
$4$ から $8$ を引くと $-4$ です。そして $10$ から $14$ を引いても $-4$ です。
さて、ここで問題です。$-4$ を $3$ で割った余りは、一体いくつでしょうか？
どのような整数でも $3$ で割った余りは $0$, $1$, $2$ のうちのどれかでなければなりません。負の余りはありませんよ。
余りについてもう一度考えておきましょう。例えば $10$ を $3$ で割った商は $3$で余りは $1$ ですね。すると次の式が成り立ちます。
$$10 = 3\times3+1$$
この式を次のように変形させます。
$$10 -3\times3=1$$ $$10 -3 -3 -3 =1$$
この意味は、 $10$ から $3$ を複数回引いていって、最初に $0$ または $1$ または $2$ になったとき、その数が余りだということです。
では $-4$ を $3$ で割った余りを考えましょう。割る数と余りは負にしてはいけません。しかし商は負にしてもいいのです。なので $-4$ は次のように表せます。
$$-4 = 3\times(-2)+2$$
この式を次のように変形させます。
$$-4 +2\times3=2$$ $$-4 +3+3=2$$
これは $-4$ に $3$ を複数回足していって最初に $0$ または $1$ または $2$ になったとき、その数が余りだということです。
つまり $-4$ を $3$ で割った余りは $2$ です。
では①, ② の合同式で差の公式どおり辺々どおしを引いてみましょう。
$4-8 \equiv 10-14 \pmod 3$
$-4 \equiv -4 \pmod 3$ ••• ③
すると ③ の式ができますが、これは同じ数になってしまったので当然ですが、余りは同じ $2$ で③の合同式は成り立っています。
積の合同式
$a \equiv c\pmod m$, $b \equiv d\pmod m$ のとき$$ab \equiv cd \pmod m$$
これも先程用意した式を使って確認しましょう。
$ 4\equiv 10\pmod 3$ ••• ①
$ 8\equiv 14\pmod 3$ ••• ②
辺どうしを掛けてみましょう。
$4\times8 \equiv 10\times 14 \pmod 3$
$ 32 \equiv 140 \pmod 3$ ••• ③
$32$ を $3$ で割った余りは $2$ です。一方 $140$ を $3$ で割った余りも $2$ ですね。確かに余りが同じになるので $4\times8$ と $10\times14$ は合同です。
積の公式の証明
ここでは証明も示してみますが、これを理解するには合同式の定義を完全に理解する必要があります。合同式の定義が「分かりにくいな」と感じていたら、ここは飛ばしてしまっても構いません。
$a \equiv c\pmod m$, $b \equiv d\pmod m$ のとき,
整数 $l$, $l’$ を用いて次のように表される。
$a-c=ml$, $b-d=ml’$ よって
$ab-cd = a(b-d)+d(a-c)=aml’+dml$
$\ \ \ \ \ \ \ \ = m(al’+dl)$
したがって $ab \equiv cd \pmod m$
証明おわり
この証明が理解できれば、和の公式と差の公式も同様な方法によって証明できます。
この証明を見てピンとこなくても心配する必要はありません。具体的な数値を使って理解できるのであれば、合同式の基本的な利用については十分です。
累乗の合同式
$a \equiv c\pmod m$ のとき$$a^k \equiv c^k \pmod m$$
累乗の公式は先程の積の公式を拡張すれば成り立つと分かります。やってみましょう。積の公式で $c$ を $a$ , $d$ を $b$ とすれば次の式が成り立ちます。
$a \equiv c\pmod m$ のとき $$a\times a \equiv c \times c \pmod m$$
これを $k$ 回繰り返していけば累乗の公式を得ることができます。
ところで「商の公式」がないのに気づきましたか？実はないわけではないのですが使わなくてもいい場面が多いのと使うには特別な注意が必要なので、ここではあえて載せていません。
実際、教科書や参考書でも商の公式は省いてある場合が多いようです。
ここでも商の公式は省きます。
合同式の利用
合同式は実際の問題を解いて慣れてしまうのが上達のコツです。
では実際に合同式を使ってみましょう。次の問題を見てください。
$37^{100}$ を $6$ で割った余りを求めよ。
合同式を知らないと、この問題はとても難しく感じます。でも合同式の公式を使えば簡単に求めることができます。
まず $37$ を $6$ で割った余りを求めます。余りは $1$ ですね。すると次の合同式が作れます。
$37 \equiv 1\pmod 6$
$37$ と$1$ は共に $6$ で割った余りが $1$ になります。余りを割った数で再び割れば、また余りになるのは当然です。ですからこの合同式が作れるのです。
さて、この余りを $1$ にしておくのがこの問題を解くキーポイントになります。計算を続けていきましょう。次に累乗の公式を使います。すると次の合同式が成り立ちます。
$37 \equiv 1\pmod 6$ だから$$37^{100} \equiv 1^{100} \pmod 6$$
$1^{100}=1$ ですから、$37^{100}$ を $6$ で割った余りは $1$ となります。
もうひとつ問題を解いてみましょう。
$n$ を $8$ で割った余りが $3$ であるとき,
$n^2+2n+5$ を $8$ で割った余りを求めよ。
$n$ を $8$ で割った余りが $3$ なので次の合同式が成り立ちます。
$n \equiv 3\pmod 8$
ここで累乗の公式と和の公式をいっぺんに使ってしまいましょう。
$ n^2+2n+5 \equiv $
$$3^2+2\times 3+5\pmod 8$$
右辺を計算します。
$ n^2+2n+5 \equiv 20 \pmod 8$
$20$ を $8$ で割った余りは $4$ なので $n^2+2n+5$ を $8$ で割った余りも $4$ です。
まとめ
合同式の計算は、いったん公式をしっかりと理解してしまえば、それほど難しくありません。
公式の意味は、その証明を理解できれば、それに越したことはありませんが、証明をみても意味が実感できない場合もあります。
だからといって丸暗記に頼るのはやめましょう。少なくとも具体的な数値を使って公式の意味を自分なりに実感しておいた方がいいのです。それを行なっておくだけで公式の身につき方が変わってきます。
