合同式の問題の解き方・合同式の性質の証明

数A

数学 2018.12.14

一見難しそうな問題でも、合同式を使うことで簡単に解けることがあります。
しかし、残念ながら合同式は数学の教科書での扱いが悪く、場合によっては教科書に掲載されていないこともしばしまです。

合同式を理解することは、整数の性質を理解するうえで非常に重要ですが、ほかの単元との兼ね合い上、どうしても授業で扱えないこともあるかもしれません。
この記事では、そんな合同式についてわかりやすくまとめます。

【目次】

１．合同式の定義

23を5で割った余りと、38を5で割った余りはともに3です。

整数を整数で割ったときには、割り切れるときと余りが出るときがありますが、割り切れるという状態を、余りが0である状態だと考えれば、すべての整数はあまりによって分類できます。

5で割った余りで考えれば、余りが0（割り切れる）、余りが1、余りが2、余りが3、余りが4という5種類に分類することができます。

言い換えれば、すべての整数は整数mを用いて、5m、5m+1、5m+2、5m+3、5m+4のいずれかの形で表すことができる、ということです。

より有名な例を挙げれば、すべての整数は偶数か奇数に分けられる、というのも2で割った余りで分類した結果です。
合同式とはこの余りによる分類を数式にしたものです。

2つの整数a, bを正の整数mで割ったときの余りが等しいとき、「aとbはmを法として合同である」といい、次のように表します。

a≡b (mod m)

具体的には、先の例でいうと

23≡38 (mod 5)

となります。日本語でいえば「23と38は5で割った余りが等しい」という意味になります。

２．合同式の性質

合同式には様々な性質があります。
簡単に言ってしまうと四則演算なのですが、これを使いこなすことで、計算が可能になります。
(ただし、除法だけはやや例外的です。詳しくはこちらの記事をご覧ください:
互いに素とは? 背理法を使った証明の例題・合同式との関係も合わせて解説)

a,b,c,d,k が整数、mが正の整数で a≡b (mod m) かつ c≡d (mod m) のとき以下のような性質が成り立つ。

基本的にこの4つが教科書や参考書で紹介されることが多い性質です。ですが、これをそのまま利用することが多くありません。

それぞれ合同式の重要な性質なのですが、実際に利用するのはもう少しわかりやすい式ばかりです。
それは、それぞれの合同式の性質の証明をした後で紹介しましょう。

s,t,u,k,l は整数とします。

①の証明

①はほとんど合同式の定義のようなものです。

aとbは合同なので

a＝sm+u
b=tm+u

というように、mで割った余りが同じであることが表せます。

a-b=(s-t)mですので、性質①のとおり、a-b がmの整数倍になっています。
またその逆も成立するので、

a≡b (mod m)⇔a-b=mk

です。

②の証明

命題の条件である

a≡b (mod m)
c≡d (mod m)

から、

a-b=mk
c-d=ml

と表すことができます。

この2つの式を足して、

(a+c)-(b+d)=m(k+l)

が成立します。①の最後で申し上げたように

a≡b (mod m)⇔a-b=mk

ですから、a+c と b-d の差がmの整数倍になっているので、a+c と b+d は、mを法として合同であることがわかります。

よって

a+c≡b+d (mod m)

が示されました。

③の証明は②とほぼ同じですので、挑戦してみてください。

④の証明

ac-bd=(b+mk)(d+ml)-bd
=bd+mdl+mdk+m²kl-bd
=m(bl+dk+mkl)

から ac-bd はmの倍数になります。よって ac≡bd (mod m) が示されました。

先にも申し上げたように、この4つは合同式の非常に重要な性質です。
ですが、本当によく使うのは、もう少し簡単な式です。

こちらの方がずいぶんわかりやすいと思います。①から④を使うことも多いですが、使用頻度や難易度でいえば、⑤と⑥の方が高いでしょう。

合同式の性質④：ac≡bd (mod m)を利用して⑤を導きます。

a≡b (mod m)

かつ

k≡k (mod m)

であることから、

ka≡kb (mod m)

となります。

⑥の証明

いろいろ証明方法はありますが、帰納的に証明します。
合同式の性質④：ac≡bd (mod m) を利用します。

a≡b (mod m)

から、

a×a≡b×b (mod m)
⇒a²≡b² (mod m)
⇒a²×a≡b²×b (mod m)
⇒a³≡a³ (mod m)

となります。これを繰り返すと、帰納的に

a≡b (mod m)　　ならば　aⁿ≡bⁿ (mod m)

が成立します。

３．合同式の問題

問
a は7で割れば3余る自然数であり、b は7で割れば4余る自然数である。このとき、次の数を7で割った余りをもとめよ。

(1) 3a+b
(2) a³
(3) b⁵⁰

解答・解説

合同式の性質を証明した時のように、a = 7n + 3、b = 7m + 4 とおいて代入しても、解くことができます。
合同式を知らなければ、そうするでしょう。
合同式を知っていれば、回答もスマートに書くことができます。
まず、「a は7で割れば3余る自然数であり、b は7で割れば4余る自然数」を以下のように表すことができるのが、合同式の魅力です。

a≡3 (mod 7)
b≡4 (mod 7)

合同式の性質の②、③、⑤はつまり、割り算以外の四則演算は普通に行ってよいことを表しています。
そして、a=3 や b=4 のように式に代入（のようなもの）ができるのも、わかりやすい性質です。
つまり(1)であれば、

3a+b≡3・3+4
≡9+4
≡13
≡6 (mod 7)

という具合です。最後の式変形以外は、合同式の記号「≡」と等号「＝」を入れ替えれば、普通の式計算になりますね。

mod 7 を付けるのを忘れないようにしてください。
mod 7 は毎回書くのが丁寧ではありますが、見やすい程度に適度につければそれで構いません。

一つの合同式に対して一つ以上はmod 7と書くのが一般的ですが、どの程度の頻度で書くかは、人によります。
そう言われると「どのくらい書けばよいかわからない」と思うでしょう。
合同式に限らず、多くの問題で「回答の書きかたがよくわからない」という声がよくあります。
ですが、多くの場合、回答の書き方に決まりはありません。

「書いてなければならないことが全て書いてあること」と「間違ったことが書いていないこと」を満たしていれば、どんな回答でもよいのです。

(2) も(1)と同様に

a≡3 (mod 7)
⇒a³≡3³
≡27
≡6 (mod 7)

となりますので、求めるあまりは6です。

(3)
次数が多い場合に利用するのが、

1ⁿ≡1 (mod m)

です。1は何乗しても1ですので、次数を一気に下げることができます。
計算していきます。

b≡4 (mod 7)
⇒b⁵⁰≡4⁵⁰
≡2¹⁰⁰
≡(2³ )³³×2
≡8³³×2
≡1³³×2
≡2 (mod 7)