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

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

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

１．合同式の定義

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 = 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)

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

回答・解説

規則性を用いても解くことができます。
一の位だけに注目すると、〖49〗ⁿ は「9, 1, 9, 1, ……」となりますので、123乗のときであれば、一の位は9であることがわかります。

累乗の一の位は循環しますので、規則性を発見すれば解くことができます。
今回はそれを使わずに、合同式を使って解こうと思います。
「一の位」を「十で割ったときの余り」と考えれば、以下のように計算できます。

〖49〗¹²³≡9¹²³
≡(9² )⁶¹×9
≡(81)⁶¹×9
≡1×9
≡9 (mod 10)

よって求める余りは9になります。

４．おわりに

最後までご覧くださってありがとうございました。
この記事では、合同式の基本と、練習問題の解説をしました。
これ以外でもさまざまな入試問題で応用され、出題されています。

場合によっては非常に簡単に問題を解くことができるようになりますので、しっかりマスターしておきましょう。