合同式って，知っていますか？
イコールのかわりに合同の記号（三本線）を使って，
a\equiv b\pmod m
のような式のことをいいます。
学生の方習った覚えないです。
習ってない人も多い合同式。教科書でも「発展」や「研究」のような扱いで，大きくは取り上げられません。
また，合同式を使わないと解けない問題というのは基本的にありません。知らなくても大学入試をクリアすることはできます。
ですが，予備校の解答速報で，合同式を平気で使ってくるケースもあるなど，意味や使い方をわかっておいて損はないと思います。
さらに，合同式を使うことで計算が大幅に楽になる問題もあります。
この機会に合同式の性質と利用法をマスターして，ドヤ顔でつかってやりましょう！
- 高校数学・高校公民・中学社会担当の現役塾講師
- 講師歴13年
- 13年の指導経験で知った「生徒がつまづきやすいポイント」や「教科書よりも効率の良い解法」をわかりやすく発信しています。
合同とは，余りが等しいということ。
合同式の定義
合同式の定義は，次のような感じです。
「aをmで割った余り」と，「bをmで割った余り」が等しいとき，
「aとbはmを法として合同である」といい，
a\equiv b \pmod m
と書きます。
粗茶さん（mod m）までがワンセットです。
「a ごうどう b モッド m」と発音されます。
合同式の具体例
例えば，25を4で割った余りと，17を4で割った余りは，どちらも1で等しいので，
「25と17は4を法として合同である」といって，
25≡17(mod 4)
と書けます。
合同式の性質
合同式は，等式と同じように，足し算・引き算・掛け算と，累乗もできます。
割り算については，条件付きでできます。
a\equiv b\pmod m，c\equiv d\pmod mのとき，
- a+c\equiv b+d\pmod m
- a-c\equiv b-d\pmod m
- ac\equiv bd\pmod m
- \color{red}kと\color{red}mが互いに素のとき，ka\equiv kb\Leftrightarrow a\equiv b \pmod m
- a^n\equiv b^n\pmod m
合同式の和と差
a\equiv b\pmod m，c\equiv d\pmod mのとき，
辺々を足して，a+c\equiv b+d\pmod m，
辺々を引いて，a-c\equiv b-d\pmod m
が成り立ちます。
証明
aをmで割った余りとbをmで割った余りは等しいので，どちらもr_1とおけて，
cをmで割った余りとdをmで割った余りは等しいので，どちらもr_2とおける。
ということで，a,b,c,dは次のように表せる。
a=ma'+r_1
b=mb'+r_1
c=mc'+r_2
d=md'+r_2
これらを用いると，
a+c=ma'+r_1+mc'+r_2=m(a'+c')+r_1+r_2，
b+d=mb'+r_1+md'+r_2=m(b'+d')+r_1+r_2
で，mの倍数でない部分がr_1+r_2で共通なので，a+cをmで割った余りと，b+dをmで割った余りは同じで，いずれも「r_1+r_2をmで割った余り」である。
つまり，
a+c\equiv b+d\pmod m
が成り立つ。
※引き算も同じなので省略
足し算と引き算については，等式と同じように移項することもできるってことです。
合同式の積
a\equiv b\pmod m，c\equiv d\pmod mのとき，
辺々をかけて，ac\equiv bd\pmod m
が成り立ちます。
証明
aをmで割った余りとbをmで割った余りは等しいので，どちらもr_1とおけて，
cをmで割った余りとdをmで割った余りは等しいので，どちらもr_2とおける。
ということで，a,b,c,dは次のように表せる。
a=ma'+r_1
b=mb'+r_1
c=mc'+r_2
d=md'+r_2
これらを用いると，
ac=(ma'+r_1)(mc'+r_2)=m(ma'c'+r_1c'+r_2a')+r_1r_2，
bd=(mb'+r_1)(md'+r_2)=m(mb'd'+r_1d'+r_2b')+r_1r_2，
で，mの倍数でない部分がr_1r_2で共通なので，acをmで割った余りと，bdをmで割った余りは同じで，いずれも「r_1r_2をmで割った余り」である。
つまり，
ac\equiv bd\pmod m
が成り立つ。
掛け算に関しても，等式と同じように扱うことができます。
合同式の両辺の割り算
a\equiv b\pmod mについて，
k（割る数）とm（合同式の法）が互いに素のときだけ，
ka\equiv kb\Leftrightarrow a\equiv b \pmod m
が成り立つ，つまり両辺の割り算ができます。
kとmが互いに素でないとき，合同式が成り立たない場合があることを，具体例で示しておきます。
例えば，
75と25は10で割った余りが5で等しいので，
75\equiv 25\pmod {10}
と書けます。
両辺を25（10と互いに素ではない）で割ると，左辺は3，右辺は1で，10で割った余りが異なります。
つまり，両辺を25で割った後は，合同式が成り立たなくなってしまうのです。
合同式の両辺を割り算するときは，割る数と法が互いに素であることを確認してからにしましょう。
ちゃんとした説明
ka\equiv kb\pmod m
⇔ ka-kb\equiv 0\pmod m
⇔ k(a-b)\equiv 0\pmod m
つまり，k(a-b)はmの倍数，
よって，k(a-b)=mX…（＊）
（Xは何かの数字）
と表される。
（ⅰ）kとmが互いに素のとき
kはmの倍数ではないので，a-bがmの倍数である。
つまり，
a-b\equiv 0\pmod m
⇔ a\equiv b\pmod m
ということで，両辺の割り算が可能である。
（ⅱ）kとmが互いに素でないとき
kとmは2以上の公約数gを持つので，
k=k'g，m=m'g
（k',m'は互いに素）
とおくことができる。
（＊）は両辺をgで割り切ることができて，
\cfrac{k}{g}(a-b)=\cfrac{m}{g}X
⇔ k'(a-b)=m'X
ここでk'とm'は互いに素なので，
a-bはm'の倍数だから，
a-b\equiv 0\pmod {m'}
⇔ a\equiv b \pmod {m'}
ということで，合同式の法が変わってしまい，mで割った余りが等しいことが保証されなくなってしまうのです。
合同式の累乗
a\equiv b\pmod mのとき，
a^n\equiv b^n\pmod m
が成り立ちます。
理由
合同式の積を利用すると，理由がわかります。
a\equiv b\pmod mなので，
a\cdot a\equiv b\cdot b\pmod m
は成り立ちます。さらに，
a\cdot a\cdot a\equiv b\cdot b\cdot b\pmod m
も成り立ちます，これは永遠に繰り返すことができるので，
かける回数をn回にして，
a\cdot a\cdots a\equiv b\cdot b\cdots b\pmod m
つまり，
a^n\equiv b^n\pmod m
もいけるよ。っていうお話。
等式と同じように，両辺をn乗しても同じになるということです。
合同式が使えると便利な問題
学生の方合同式の存在はわかったけど，実際の問題でどうやって使えるの？
ここからは，合同式を使うことで計算が簡単になる場合を紹介しましょう。
合同式の現実的な使い方は「余りへの置き換え」
合同式の定義は最初に述べたとおりですが，現実的には「余りに置き換える」使い方が有効です。
aをmで割った余りがr（r<m）であることを，
a\equiv r \pmod m
と表記する場合が多い。
例えば，「aを5で割った余りが2」であるとき，
a\equiv 2 \pmod 5
と書くことができます。
実際の問題を扱いながら，合同式の使い方を紹介しましょう。
累乗の余り
まずは，累乗の数を何かで割った余りを求めるときの計算です。
15^{2023}を7で割った余りを求めよ。
2023乗を計算することは不可能ですが，余りを求めればよいだけなので，余りに注目した計算をすればOKです。
標準的解答
15=7\cdot 2+1より，
\begin{aligned}
&15^{2023}\\\\
＝&(7\cdot 2+1)^{2023}\\\\
＝&{\color{red}_{2023}{\rm C}_0(7\cdot 2)^{2023}+_{2023}{\rm C}_1(7\cdot 2)^{2022}\cdot 1^1+_{2023}{\rm C}_2(7\cdot 2)^{2021}\cdot 1^2+\cdots }+_{2023}{\rm C}_{2023}\cdot 1^{2023}\\\\
＝&{\color{red}\text{(7の倍数)}}+1^{2023}\\\\
\end{aligned}粗茶さん二項定理で展開しています。
よって，求める余りは，1^{2023}＝1を7で割った余りなので，1 …（答）
合同式を使った解答
本質的には変わらないのですが，合同式を用いると，余りだけに注目できるので，計算が易しくなります。
15を7で割った余りは1，つまり，
15\equiv 1\pmod 7 なので，
15^{2023}\equiv 1^{2023}=1\pmod 7
15^{2023}\equiv 1 \pmod 7
なので，15^{2023}を7で割った余りは1 …（答）
余りが１になるときでないと使いづらいですが，余りだけに注目すればいいという意味では，合同式はとても有効です。
和や積の余りの問題
また，余りを扱った問題でも，合同式を導入することで早く解くことができます。
a,bは整数とする。
aを7で割った余りは3，bを7で割った余りは4である。
（1）a+2bを7で割った余りを求めよ。
（2）abを7で割った余りを求めよ。
標準的解答
a=7m+3，b=7n+4とおける。
（１） a+2b
＝7m+3+2(7n+4)
＝7m+14n+11
＝7m+14n+7+4
＝7(m+2n+1)+\color{red}4
よって，求める余りは\color{red}4 …（答）
（２） ab
＝(7m+3)(7n+4)
＝49mn+28m+21n+12
＝49mn+28m+21n+7+5
＝7(7mn+4m+3n+1)+\color{red}5
よって，求める余りは\color{red}5 …（答）
よくある問題で，特に悪いところはないのですが，mとかnがついている項は必ず7の倍数だから，余りを求める時には関係ありません。
そこで合同式を使うと，余りの部分だけに注目できるので，余分な計算をしなくてすみます。
合同式を使った解答
粗茶さん毎回（mod 7）って書くのが面倒な場合は，最初に合同式の法を宣言しておくと，（mod 7）を省略できます。
合同式は7を法とする。
a\equiv 3，b\equiv 4
とおける。
（１） a+2b
\equiv 3+2\cdot 4
=11
\equiv 4
よって，求める余りは\red 4 …（答）
（２） ab
\equiv 3\cdot 4
=12
\equiv 5
よって，求める余りは\red 5…（答）
合同式を使うと，余りにだけ注目できるので，計算も簡潔にすみます。
2元1次不定方程式を合同式で解く
2元1次方程式は，合同式を用いて解くこともできます。
方程式7x-13y=1をみたす整数x,yの組を求めよ。
よくある方法
ユークリッドの互除法を用いる。
13=7\cdot 1+6 …①
7=6\cdot 1+1 …②
①より，6=13-7\cdot 1 …①’
②より，1=7-6\cdot 1
①’を代入して，
1=7-(13-7\cdot 1)\cdot 1
⇔7\cdot 2-13\cdot 1=1 …（＊）
元の式から（＊）を引いて，
7(x-2)-13(y-1)=0
⇔7(x-2)=13(y-1)
ここで右辺は13の倍数である。等式が成り立つためには左辺も13の倍数でなくてはならない。
7と13は互いに素であり，7は13の倍数ではないので，x-2が13の倍数である。
よって，x-2=13k（kは整数）とおくことができ，上の式に代入することで，
y-1=7k も成り立つ。
よって，(x,y)=(13k+2,7k+1)，ただしkは整数 …（答）
一般的な方法を書きました。やったことのある人は，x,yの組を１つ見つけるのが面倒に思うことでしょう。
実は，合同式を使うことで，いきなり一般的な答えを求めることができてしまいます。
合同式を用いて解く方法
7x-13y=1
⇔ 13y=7x-1
ここで，7x-1は，7で割ると6余る数なので，
7x-1\equiv 6\pmod 7
って書けます。
7x-1と13yは等しいので，
13y\equiv 6\pmod 7…（＊）
も成り立ちます。
これをうまく変形して，yの係数が1になるようにします。
13yを7で割った余りは，13y-7yを7で割った余りは等しいので，7の倍数を足したり引いたりしても合同なので，
13y\equiv 13y-7y\equiv 6y\pmod 7
これを（＊）の左辺に代入（という表現でいいのか怪しい）して，
6y\equiv 6\pmod 7
両辺を6（7と互いに素）で割って，
y\equiv 1\pmod 7
つまり，yを7で割った余りが1ということなので，
\color{red}y=7k+1（kは整数）
である。
これを最初の式に代入して，
7x-13(7k+1)=1
⇔ 7x=13\cdot 7k+14
∴ \color{red}x=13k+2（kは整数）
合同式を使うと，いきなり答えにたどり着くことができますが，計算に慣れる必要はありそうですね。
合同式を利用して，効率よく解答を作ろう
この記事では，合同式の性質と，実際の問題への利用方法を紹介しました。
要点をまとめると以下のとおりです。
- 合同とは，余りが等しいという関係のこと。
- 合同式は，方程式のように移項や累乗ができるが，割り算だけは注意が必要。
- 余りに関する問題を解く際に，合同式が力を発揮する。
初めは慣れないかと思いますが，使い方をマスターすると，問題を解く上での強力な武器になります。
数学の知識で，知ってて損なことはありませんので，ぜひ身につけてほしいところです。
このブログでは，自分で勉強しているとき，つまづきやすいポイントを解説。
「かゆいところに手が届く」情報を発信しています。
自分で勉強する際にオススメの参考書や，勉強が楽しくなる文房具も紹介していますので，よろしければご覧ください！
コメント