㉖ 数学四方山話 2 合同式

　問）「3で割ったたら1余り、5で割ったら2余り、7で割ったら3余る数は何ですか？」

　まず記号を導入します。数式というとアレルギーになる方が多いと思いますが、（実は筆者もその一人です）前にも述べたように、多数回接して「常識」になってしまえば大したことはありません。

　整数aと bがあり、 mで割った余りが等しい時、 a≡b(modｍ)と書きます。「a合同bモッドm」と読みます。mを法と言います。これはa－ bが mの倍数という条件と一致します。また、”aをmで割ったらb余る”と言っても同じことです。以下a＝ km+ b、c＝ lm+ dと置いて簡単に確かめられることですが、合同式の性質を列挙します。

　1) a≡ b （mod m）、c≡d（mod m)なら, a± c≡b± d（mod m)と言ってもよいのです

2) ac≡ bd（mod m )

3)aの n乗＝ bの n乗(mod m)

ごちゃごちゃしているようですが、modさえ同じなら（これ重要です！）、左辺は足し算、引き算、掛け算が自由にできるということです。ただし割り算は無条件にというわけにはいかず、aとmとが互いに素である（共通因数がない）場合に限り、ax≡ ay（mod m)なら x≡y（ mod m)が成り立ちます。

　つまりaを mで割ったら余りがpとなった時、 a≡ p（mod m)と書くのです。

　さてこれを前提条件として、問を書き表してみましょう。

　その数をxとすると 、

　x ≡1(mod 3)～xを3で割ると余りは1。

　x ≡2(mod 5)

x ≡3(mod 7)となりますね。ただし、modが揃っていません。そこで一工夫します。

x ≡1(mod 3)は 、x＝3 n+ 1でした。2倍すると2x＝6n＋2、3倍すると3x＝ 9n+ 3ですつまり x≡1(mod 3)は 、2x≡2(mod 6)、3x≡3(mod 9)となっています。そこで三つのmodを揃えます。3、5、7の最小公倍数は105ですから、書き直すと

35x≡ 35(mod 105)・・・1)

21x≡ 42 (mod 105)・・・2)

15x≡ 45(mod 105) ・・・3)

これでmodが揃いましたので、左辺は加、減、乗ができます。

1)- 2) 14x≡- 7(mod 105)・・・4)

15x ≡45 (mod 105)・・・3)ですから

3)- 4) x≡52(mod 105)、つまり、 x＝ 105 n+ 52 、(n＝0、１、2...　)

　もう少し巧妙な方法もあります。まず、5でも7でも割り切れるが(35の倍数)、3で割ると1余る数を探します。70ですね。次に同様にして3、7で割り切れるが5で割ると1余る数、21。次に、3,5で割り切れるが、7で割ると1余る数、15。だから題意の数は、70x1+21x2+15x3＝167。ここから、3でも5でも7でも割り切れる数105（これは余りに関係しません）を引くと52。（答）いかがですか？

もちろん大きな数になると、そこからいくらでも105を引けばよいのです。ちなみにn＝0を入れてみましょう。52＝3x 17+ 1余り1、 52＝5x10+2余り2、52＝7x7+3 余り3、たしかにあっています。いかがですか？簡単に求まったでしょう。この手の問題には合同式を使えばよいのです。もちろん合同式には色々の応用があります。「余り」と来たら合同式をまず思い浮かべてください。