合同式って，知っていますか？
イコールのかわりに合同の記号（三本線）を使って，
a\equiv b\pmod m
のような式のことをいいます。
学生の方習った覚えないです。
習ってない人も多い合同式。教科書でも「発展」や「研究」のような扱いで，大きくは取り上げられません。
また，合同式を使わないと解けない問題というのは基本的にありません。知らなくても大学入試をクリアすることはできます。
ですが，予備校の解答速報で，合同式を平気で使ってくるケースもあるなど，意味や使い方をわかっておいて損はないと思います。
さらに，合同式を使うことで計算が大幅に楽になる問題もあります。
この機会に合同式の性質と利用法をマスターして，ドヤ顔でつかってやりましょう！
粗茶
- 文系に特化して数学を分かりやすく教える高校数学の専門家
- 指導歴14年
- 数学が苦手で何から始めたらいいか分からない文系高校生の悩みを解決するコンテンツを展開しています。
理解を深めたい人は，映像での学習もオススメ。スタディサプリ高校講座は，14日間無料体験実施中！
合同とは，余りが等しいということ。
合同式の定義
合同式の定義は，次のような感じです。
「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は整数）
合同式を使うと，いきなり答えにたどり着くことができますが，計算に慣れる必要はありそうですね。
合同式を利用して，効率よく解答を作ろう
この記事では，合同式の性質と，実際の問題への利用方法を紹介しました。
要点をまとめると以下のとおりです。
- 合同とは，余りが等しいという関係のこと。
- 合同式は，方程式のように移項や累乗ができるが，割り算だけは注意が必要。
- 余りに関する問題を解く際に，合同式が力を発揮する。
初めは慣れないかと思いますが，使い方をマスターすると，問題を解く上での強力な武器になります。
数学の知識で，知ってて損なことはありませんので，ぜひ身につけてほしいところです。
このブログでは，自分で勉強しているとき，つまづきやすいポイントを解説。
「かゆいところに手が届く」情報を発信しています。
自分で勉強する際にオススメの参考書や，勉強が楽しくなる文房具も紹介していますので，よろしければご覧ください！
