合同式の意味や【mod】の性質/実際の使い方を分かりやすく解説

合同式:modとは?

今回は合同式（と関連する『〜を法として〜』や『合同』、『≡』の意味など）について始めから解説していきます。

合同式は「名前は聞いたことがあるけどよくわからない」、「難しそう」といった印象を持っている人もいるかと思います。

また、学校でしっかり教えて貰わなかった！と言う生徒もいます。

慣れれば整数問題を解く際にたいへん便利な物なので、ぜひこの記事で基礎を身に付けて下さい！

合同式とは

2つの異なる数を同じ数で割った時、その余りが同じものを合同の記号である「≡」で表したものです。

具体的な数字を用いて説明していきます。

17と9は「4」という数で割った時、余りが1で同じです。実際計算してみると、

17÷4=4余り1 又 9÷4=2余り1

この時合同式を使って、17≡9 (mod 4)と書き、

「17と9は4を法として合同」という風に言います。意味は「17と9は4で割った余りが同じ」です。

このままでは何が便利なのかよくわからないと思うので、合同式の四則演算を解説してからその威力を紹介します。

合同式の四則演算

合同式は、和(+)、差(-)、積(×)に関しては普通の式と同様に計算できます。実例と共に見ていきます。

今、13≡17(mod4)  と11≡3(mod4)

がある時、

和・差・積

和：13+11≡17+3≡0 (mod4)となり、

差：13-11≡17-3≡2 (mod4)

積：13・11≡17・3≡3(mod4)

でいずれの場合も確かに成立しています。

合同式の割り算の成立条件

しかし、商(割り算)だけは、常に成り立つわけではなく、”割る数”と”法とする数”が互いに素な時のみ成立します。

modの性質を一般化したまとめ

これらを文字式で表すと

m≡n(mod A)、p≡q(modA)の時

$$\begin{aligned}m\equiv n\left( modA\right) \\
p\equiv q\left( modA\right) \end{aligned}$$

和と差

$$\begin{aligned}m+p\equiv n+q( modA) \\
m-p\equiv n-q( modA) \end{aligned}$$

整数倍

mp≡nq (modA)

べき乗

更に、m^c≡n^c (modA)

$$\begin{aligned}mp\equiv nq( modA) \\
m^{c}\equiv n^{c}( modA) \end{aligned}$$

以上のことに注意して、例題に入ります。

合同式modの使い方(問題編)

次のような問題で、modを使う方法を具体的に紹介していきます。

例題：2^50を5で割った時の余りを求めよ。

まさか本当に50乗する訳にはいかないので、2つの解法を思い浮かべます。

(解法案1-1)規則性を見つける。

2^1/5=0余り2

2^2/5=0余り4

2^3/5=1余り3

2^4/5=3余り1

2^5/5=6余り2

2^6/5=12余り4

・・・

どうやら、2、4、3、1、　2、4、3、1 という規則がありそうです。

しかしこれでは底である2が大きな数字になった時、時間がかかり過ぎて実践的ではありません。

そこで、

(解法1-2)合同式を利用する

ここでは\(2^{50}=( 2^{4}) ^{12}\times 4\) と変形出来ます。

＜『指数の計算』については→「指数・対数とは？」で解説しています＞

(2^4)に注目して、2⁴=16 、16÷5=3余り1 、 1÷5=0余り1、

つまり、５で割った時１６＝２^４と１の余りは同じになります。

すなわち5を法とすると、2⁴=16と1が合同であると言えるから、2⁴≡1(mod 5) と表せます。

\(2^{4}\equiv 1\left( mod5\right) \)

従って

\(2^{50}=(2^{4})^{12}\times 4\equiv 1^{12}\times 4=4(mod5) \)

よって余りは4と求めることが出来ました。

合同式まとめ：巨大な数をどんどん小さい数へ

ということが、この類の問題を解く時に一番大切です。

そして、その過程で底となる数（今回は２）の何乗かが、法の数の倍数と比べた時（５の倍数）

±１や０等簡単な数字になるようにうまく”べき乗”を作ってやるとうまく解くことが出来ます。

この様にして、普通では計算できない様な数を扱える事が合同式の最大の強みと言えます。

整数分野・関連記事のまとめへ

他にも整数分野ではあちこちで合同式を使うとスムーズに回答できる問題があるので、逐次記事を追加して行きます。

ジャンルは違いますが、大きな数の桁数や最高位の数字を求める方法をまとめた記事を作成しました。

→「常用対数を使って桁数や最高位の数を求める方法」を読む。

＞＞整数問題の解法１０選「センス・閃きなしで整数を攻略する方法」に戻る＜＜

今日も読んでくださり有難うございました。

お役に立ちましたら、SNSボタンでシェアお願いします！