《　　ａ＝ｂ　と　ａ≡ｂ　　》

−方程式と似ている合同式−

　もう数年も前のことであるが、中学１年生から次のような問題についての説明を求められたことがある。

Ａ中学校前を通ってＢ駅まで行くバスは３系統ある。午前９時から午後５時までの間、系統番号�@のバスは８分間隔、系統番号�Aのバスは１２分間隔、系統番号�Bのバスは１５分間隔で走っている。　そして、午前９時にこれら３系統のバスは同時にＡ中学校前のバス停を出発する。 　ある日、系統番号�@のバスだけ発車時刻の１分前にＡ中学校前のバス停に到着していた。たとえば午前９時７分に到着し、午前９時８分に発車していた。このとき系統番号�@のバスの到着と同時に発車していくバスは午前９時から午後５次まで何台あったか。また３系統のバスが同時に発車することはこの日にはあり得るか。

　中学１年生のしかも初期の段階では、文字代数による解法ではなく、最大公約数や最小公倍数の性質を使って解くのであろうが、説明には大変苦労する。高校でも整数の問題として興味深い教材になり得る。整数に関する問題を合同式の性質を用いるとすっきり解ける。そのような問題は少なくないが、現在の高校ではそこまで深入りせずに整数教材を扱っている。しかし、ここではあえて合同式の性質を考えつつ上の問題を考えてみることにしよう。

　整数ａ，ｂをそれぞれ正の整数ｍで割って等しい余りｒを得たとする。ｑ₁，ｑ₂を商として、
　　ａ＝ｍｑ₁＋ｒ，　ｂ＝ｍｑ₂＋ｒ　　(０≦ｒ＜ｍ)
　　　これより、ａ−ｂ＝ｍ(ｑ₁−ｑ₂)
　ここでｑ₁-ｑ₂は整数なので、これをｋとおくとａ−ｂ＝ｍｋとなり、ａ−ｂはｍの倍数となる。ガウスはこれを次のように表した。
　　　ａ≡ｂ　(mod　ｍ)
　そこで、次のように定義している。

２つの整数ａ，ｂはａ−ｂがｍの倍数であるとき、ｍを法として合同であるといい、ａ≡ｂ　（mod　ｍ）と表し、これを合同式という。

【１】ａ，ｂ，cを整数とするとき、 　（�T）　ａ≡ａ 　（�U）　ａ≡ｂ (mod　ｍ)　ならば　ｂ≡ａ　(mod　ｍ) 　（�V）　ａ≡ｂ (mod　ｍ)， ｂ≡ｃ　(mod　ｍ)　ならば　ａ≡ｃ (mod　ｍ)

　証明は省略するが、（�T）を反射律、（�U）を対称律、（�V）を推移律と呼び、（�T）（�U）（�V）の３つの性質を持つ関係を同値関係と呼んでいる。同値関係を満たすある関係が与えられると、ある集合をこの関係に基づいて、互いに共通部分を持たない空でない部分集合の合併として表すことができる。つまり、集合の要素を分類して共通な性質を持った要素ごとにまとめるいことができるわけで、数学ではこれを類別と呼んでいる。更に合同式では次の定理が成立する。

【２】　ａ≡ｂ (mod　ｍ)，　ｃ≡ｄ (mod　ｍ)　のとき 　（�T）　ａ＋ｃ≡ｂ＋ｄ　　　（�U）　ａ−ｃ≡ｂ−ｄ　　　（�V）　ａｃ≡ｂｄ

　以上の性質を利用すると、更に次のことも成り立つ。（証明は略）

【３】　ａ≡ｂ (mod　ｍ)で、ｃを整数、ｎを正の整数とする。 　（�T）　−ａ≡−ｂ 　　（�U）　ａ±ｃ≡ｂ±ｃ　　（�V）　ａｃ≡ｂｃ　　 (�W) ａｎ≡ｂｎ

　以上の諸性質は等号の＝についても成り立つ性質である。このことは合同式としての≡と等号の＝とは形の上での演算としては、非常に似た性質を持っていることになる。方程式を解いたりするのも等式のいろいろな性質を用いながら計算しているわけなので、似た性質を持つ合同式についても、ほとんど方程式を解くのと同じようにして計算できるわけである。いくつかの例を考えてみよう。

ｐは７で割ると５余り、ｑは７で割ると４余る整数とする。このとき次を７で割ったときの余りを求めよ。 　(1)　ｐ−２ｑ　　　　　(2)　ｐｑ　　　　(3)　ｑ20

（解）　ｐ≡５ （mod　７）　　ｑ≡４ (mod　７)　
　(1)　ｐ−２ｑ≡５−２×４≡４ (mod　７)　　よってｐ−２ｑは７で割ると４余る。
　(2)　ｐｑ≡５×４≡６ (mod ７)　　よってｐｑは７で割ると６余る。
　(3)　ｑ³≡４×４×４≡１　(mod　７)　より
　　　　　　(ｑ³)⁶・ｑ²≡１⁶・４²≡２　(mod　７)
　　　よって　ｑ²⁰は７で割ると２余る。

　ある大学で出題された次のような問題も、なかなか考えづらい問題の部類にはいると思われる。これも合同式を使うとすっきりと、しかも明解に説明してゆくことができる。

３８５より小さい自然数ｘを５，７，１１で割った余りをそれぞれ ａ，ｂ，ｃとするとき、２３１ａ＋３３０ｂ＋２１０ｃを３８５ で割った余りはｘに等しいことを示せ。

（解）　ｐ＝２３１ａ＋３３０ｂ＋２１０ｃ　とおく。３８５＝５×７×１１に注意。
　まずｐを５，７，１１で割った余りを求める。それはａ，ｂ，ｃである。よって、
　　　ｐ≡ａ (mod　５)，　　ｐ≡ｂ (mod　７)，　　ｐ≡ｃ (mod　１１)
　また、題意より
　　　ｘ≡ａ (mod　５)，　　ｘ≡ｂ (mod　７)，　　ｘ≡ｃ (mod　１１)
　ゆえに、
　　　ｐ−ｘ≡０　(mod　５)，　　ｐ−ｘ≡０　(mod　７)，　　ｐ−ｘ≡０　(mod　１１)
　これより、ｐ−ｘは５，７，１１で割り切れるから、５×７×１１で割り切れる。
　　　ｐ−ｘ≡３８５ｋ　（ｋは整数)　　∴　ｐ＝３８５ｋ＋ｘ
　よって、ｐを３８５で割った余りはｘである。

　次の入試問題も合同式を使いながら解いていくと簡単にできるが、そうでない解法だとかなり考えづらい問題となろう。

自然数で３で割ると２余り、５で割っても２余り、７で割ると５余るものは無数にあるが、このち最小のものは（　　　　）であり、一般には 　　（　　　　　）l+（ 　　　　） という形に表せる。 　ｌは０または自然数である。

（解）　ｎ−２≡０ (mod　３)…�@，　ｎ−２≡０ (mod　５)…�A，　ｎ−５≡０ (mod　７)…�B
　�@，�Aより　ｎ−２は３，５で割り切れるから１５で割り切れる。
　　　　∴　ｎ−２≡１５ｋ　…�C　　これを�Bに代入して、
　　　１５ｋ−３≡２×７ｋ＋ｋ−３≡ｋ−３≡０　(mod　７)
　　　　∴　ｋ−３≡０ (mod　７)
　　ゆえに、ｋ−３≡７ｌ　　　　∴　ｋ＝３＋7ｌ
　　これを�Cに代入して
　　　　ｎ＝１５(３＋７ｌ)＋２＝４７＋１０５ｌ
　　ｌ＝０を代入して題意に適する自然数の最小のものは４７である。

　ある整数の1の位の数字は、その整数を１０で割った余りを求めるとよい。一般に整数ａの１の位の数字はａ≡ｒ (mod　１０) となるｒ(ｒ＝０，１，２，…，９) を求めるとよい。

１９８７1987の１の位の数字を求めよ。

（解）　ａ＝１９８７とすると　ａ≡７ (mod　１０)
　　　ａ²≡７²≡９　(mod　１０)，　　ａ³≡７×９≡３　(mod　１０)
　　　ａ⁴≡３×７≡１ (mod　１０)
　よって、ａ¹⁹⁸⁷≡(ａ⁴)４９６・ａ³≡１⁴⁹⁶・ａ³≡ａ³≡３(mod　１０)
　ゆえに、１９８７¹⁹⁸⁷の１の位の数字は３である。

　普通の方程式だと４ｘ＝１２よりｘ＝３となるが、合同式で４ｘ＝１２　(mod　ｍ)よりｘ≡３　(mod　３)とできるだろうか。これについては次のような性質がある。

【４】　ｋａ≡ｋｂ (mod　ｍ)のとき 　（�T）　ｋとｍが互いに素ならば ａ≡ｂ (mod　ｍ) 　（�U）　ｋとｍの最大公約数をｄとすると　ａ≡ｂ (mod　ｍ/ｄ)

　証明は省くが、上の性質【４】は合同式と普通の等号とで著しく異なっている性質である。また、これを証明は省くが、次の【５】の性質も等号とは異なった性質といえる。

【５】　ａ＞１でａとｍが互いに素とする。 　ａｘ≡ｂ (mod　ｍ) は ｍ＝ａｑ±ａ1　とおくと、ａ1ｘ≡±ｂｑ　(mod　ｍ)　と変形できる。

　さて、いよいよ最初の問題を合同式を使って解くことを考えよう。

　午前９時から午後５時までの間は８時間（４８０分）である。１５分間隔で発車するとは１５の倍数を考えていくとよい。また�@のバスだけ到着するのが予定発車時刻のいつも１分前である。従って�@のバスの到着時刻については８で割って７余る数の集合を考えていくとよい。�@の到着時刻と�Bの発車時刻が同時である、或いは�@の到着時刻と�Aの到着時刻が同時であるとは次のような問題として考えていくとよい。

(1)　１から４８０までの自然数において８で割ると７余る数が１５の倍数と一致するのはどんな場合か。 (2)　１から４８０までの自然数において８で割ると７余る数が１２の倍数と一致するのはどんな場合か。 (3)　上の(1)，(2)は同時に起こり得るか。

（解）　(1)　１≦ｎ≦４８０として　ｎ≡７ (mod　８)、ｎ≡０ (mod　15)　である。
　よって、ｎ＝１５ｋ (ｋは整数)。従って　１５ｋ≡７　(mod　８)、１６ｋ−ｋ≡７　(mod　８)
　　　　∴　ｋ≡−７≡１　(mod　８)
　　　　∴　ｋ≡１＋８ｍ (ｍは整数)
　　　　∴　ｎ＝１５(１＋８ｍ)＝１５＋１２０ｍ，　ｎ＝１５＋１２０ｍ≦４８０
　　　　∴　ｍ≦３
　　　ｍ＝０，１，２，３　に対してｎ＝１５，１３５，２５５，３７５
　よって、９時１５分、１１時１５分、１３時１５分、１５時１５分に�@の到着時刻と�Bの発車時刻は一致する。

(2)　ｎ≡７ (mod　８)、ｎ≡０ (mod　１２)　　ゆえに　ｎ＝１２ｋ　　∴　１２ｋ≡７ (mod　８)
　　　８Ｋ＋４ｋ≡４ｋ≡７　(mod　８)　　∴　４ｋ≡７　(mod　８)
　これは【４】や【５】のどの性質にも当てはまらない。このとき、ｋ≡ａ　(mod　８)　となるａは存在しないことは次の表ですぐわかる。

　よって４ｋ≡７となるｋは存在しない。従って、８で割ると７余る数が１２の倍数と一致することはない。つまり、�@の到着時刻と�Aの発車時刻が一致することはない。以上より�@の到着時刻と同時に発車するのは�B系統で４回だけ起こる。

　証明は省くが、次の合同式の性質も重要である。

【６】　ａｘ≡ｂ　(mod　ｍ) のとき 　（�T）　ａとｍが互いに素のときは、一つの解を持つ。 　（�U）　ａとｍの最大公約数ｄが１より大のとき、ｂがｄで割り切れるときに限って解を持つ。

　この【６】の性質を用いて上記問題の（�U）を次のように解くことができる。

　途中過程は省略して、４ｋ≡７　(mod　８)。これは【６】【５】のどの性質にも当てはまらないことは、すでに述べた。【６】の（�U）の性質によると４と８の最大公約数は４である。このとき、７が４で割り切れるときのみ解を持つが、７は４で割り切れない。
　よって、４ｋ≡７　(mod　８)は解を持たない。

　以上のように整数を他の整数で割って割り切れるとか、どのような余りがでるとか、それらに関する複雑な問題を合同式を用いて、しかも方程式を計算するごとくに式を操作して考えていくことができ、思考を楽に、しかも深く追求してゆくことができる。