本記事の内容
本記事は、整数のグループ分けの手法の一つとして、合同式について解説する記事です。
本記事を読むに当たり、割り算定理について知っている必要があるため、以下の記事も合わせてご覧ください。
合同式とは？
筆者が高校生の頃は合同式は高校数学の範疇ではありませんでした(確かそうだったはず…)が、今や合同式は高校数学で学んでいる内容です。
故に、「合同式って何？」という質問にはたくさんの方が答えられると思います。
しかし、それは厳密でしょうか？
合同式ってなんでしょうか？
a≡b (mod m)のような式です。
例えばどんなのがありますか？
5≡3 (mod 2)などですね。
では、先程の式a≡b (mod m)のa,b,mの条件は何でしょう？
a,b∈Zで、m∈Nです。
では、先程の式a≡b (mod m)のa,b,mの意味は何でしょう？
a−bがmの倍数という意味です。
確かに先程の例5≡3 (mod 2)は5−3=2×1で5−3は2の倍数ですね。
しかし、a≡b (mod m)が「a−bがmの倍数という意味」であれば、5−3=(−1)×(−2)と書くこともできますが、m∈Nだとするとこの場合は考えないのですか？
え…どうでしょう…（タスケテ…）
またまた登場！助け舟を出そう！
確かに、m∈Nでなければいけないのでしょうか？
「mの倍数」という文言が出現する以上、0は排除してm≠0であるのはわかりますが、m>0でなければならないのでしょうか？
実は、m∈Z∖{0}で良いのです。
合同式とは何か？(厳密な話)
確かに、高校ではm∈Nと習ったかもしれません(筆者は高校で合同式を習っていないので定かではありませんが…)。
しかし、Aくんの指摘通り5−3=(−1)×(−2)とも書けるため、m∈Nでなくとも良いのではないでしょうか。
答えは、
です。
つまり、mは0以外の整数であれば何でも良い、マイナスでも良い、ということです。
厳密に明示しましょう。
合同式
m∈Z∖{0}とする。a,b∈Zであり、a−bがmで割り切れる、すなわち (∃k∈Z) s.t. a−b=km となるとき、a≡b (mod m)と書き、aとbはmを法として合同という。また、a≡b (mod m)という形式の式を合同式という。mod？
(mod )はmodulusのmod。すなわち、5≡3 (mod −2)という式も成り立つ、というわけです。
合同式の間違った解釈
a≡b (mod m)は
(∃k∈Z) s.t. a−b=km
が成り立つことだ、と説明しました。
ではこの式の意味は何でしょうか？
少々変形すると、
(∃k∈Z) s.t. a=km+b
となります。
「お！これ、割り算定理の形じゃん！」となるのではないでしょうか。
ここで、割り算定理(剰余の定理)とは以下でした。
定理0.(割り算定理、剰余の定理)
a,b∈Zとする。b>0であるならば、 a=qb+r(0≤r<|b|) となるような整数q,rがa∈Zに対して一意的に存在する。割り算定理(剰余の定理)の証明は【代数学の基礎シリーズ】初等整数論編 その2をご覧ください。
確かに、割り算定理と似た形をしています。
さて、同じでしょうか？
実は、似て非なるものです。
たとえば、最初に挙げた例
5≡3 (mod 2)
を見てみると、
5−3=2×1⟺5=1×2+3
となり、たしかに割り算定理の形をしています。
割り算定理においてa=5、q=1、b=2、r=3です。
しかしながら、割り算定理はrの条件が0≤r<|b|です。
r=3>2=bとなり、この条件を満たしません。
したがって、
ということになります。
合同式の意味は？
では、a≡b (mod m)の意味とは何でしょうか？
答えは次の命題です。
命題1.
a,b∈Z、m∈Z∖{0}とするとき、a≡b (mod m)であることと、aおよびbをmで割った余りが等しいことは同値である。要するに、a≡b (mod m)が成り立つと言われたらば、「aをmで割った余りとbをmで割った余りが等しいってことだ」というわけです。
命題1.の証明
割り算定理(剰余の定理)から、
a=qm+r,b=q′m+r′
と書くことができます。
ただし、q,r,q′,r′∈Zであり、0≤r<|m|かつ0≤r′<|m|です。
①a≡b (mod m)⟹aおよびbをmで割った余りが等しいことの証明
a≡b (mod m)であれば、
(∃c∈Z) s.t. a−b=mc
です。
今、
a−b=qm+r−(q′m+r′)=m(q−q′)+r−r′
であるため、a≡b (mod m)であれば、
(∃c∈Z) s.t. m(q−q′)+r−r′=mc
ということになります。
故に、(∗)を変形して
r−r′=m(c+q′−q)
です。
仮に、r≠r′、すなわちr−r′≠0だとします。
m∈Z∖{0}によりm≠0ですから、このときc+q′−q≠0となります。
c,q′,q∈Zにより、c+q′−q∈Zです。
そしてc+q′−q≠0であるから、c+q′−q≥1またはc+q′−q≤−1です。
したがって、|c+q′−q|≥1となります。
故に、
|m(c+q′−q)|≥|m|
となります。
しかしながら、0≤r<|m|かつ0≤r′<|m|であったため、−|m|<r−r′<|m|です。
すなわち、
|r−r′|<|m|
です。
故に、r−r′=m(c+q′−q)に矛盾です。
したがって、r=r′です。
②aおよびbをmで割った余りが等しい⟹a≡b (mod m)の証明
逆に、r=r′であれば、a−b=m(q−q′)となるため、a≡b (mod m)です。
命題1.の証明終わり
整数の合同はZをクラス分けします。
Zは言わずもがな無限集合(要素が無限個の集合)です。
要素の個数が有限でないことの恩恵もありますが、無限個のものの特徴を捉えるのは難しいものです。
実は、整数の合同はZを有限個のクラス(グループと言っても良いでしょう)に分けることができます。
「クラス分け？お？もしかしてアレか？」となった方、鋭いです。
その通り、整数の合同≡は同値関係なのです。
同値関係と同値類の軽い復習
同値関係
一般に、次の３条件を満たす集合X上の関係∼を同値関係(equivalence relation)という。- x∈Xのとき、x∼x(反射律),
- x,y∈Xのとき、x∼y⇒y∼x(対称律),
- x,y,z∈Xのとき、x∼y, y∼z⇒x∼z(推移律)
定理2.
x∈Xと同値な要素全体をCxと書き、これをxの同値類(equivalence class)という。すなわち、 Cx={y∈X∣x∼y} である。 このとき、次が成り立つ。- x∈Cx,
- Cx∩Cy≠∅⇒Cx=Cy,
- Cx≠Cy⇒Cx∩Cy=∅.
詳しくは、【論理と集合シリーズ】その7を御覧ください。
そもそも整数の合同≡は二項関係なのか？
二項関係です。
実際、
Rm={(x,y)∈Z|(∃k∈Z) s.t. x−y=mk}
としたとき、(a,b)∈Rmをa≡b (mod m)と書いている、と捉えることができるからです。
整数の合同≡は同値関係なのか？
同値関係です。
命題3.
整数の合同≡は同値関係である。すなわち、任意のa,b∈Z、任意のm∈Z∖{0}に対して- 反射律 a≡a (mod m)
- 対称律 a≡b (mod m)⟹b≡a (mod m)
- 推移律 a≡b (mod m) ∧ b≡c (mod m)⟹a≡c (mod m)
命題3.の証明
①反射律の証明
a−a=0=0×mにより、a≡a (mod m)です。
②対称律の証明
a≡b (mod m)とすると、
(∃k∈Z) s.t. a−b=mk
です。
このとき、
b−a=m×(−k)
であり、当然−k∈Zであるため、b≡a (mod m)です。
③推移律の証明
a≡b (mod m)かつb≡c (mod m)とします。
すなわち、
(∃k1∈Z) s.t. a−b=mk1(∃k2∈Z) s.t. b−c=mk2
とします。
このとき、
a−c=a−b+b−c=mk1−mk2=m(k1−k2)
となるため、a≡c (mod m)です。
したがって、整数の合同≡は同値関係です。
命題3.の証明終わり
この同値関係≡の同値類に着目してみます。
整数の合同≡の同値類に着目してみます。
体裁を整えるために、
a∼b⟺a≡b (mod m)
と書きます。
このとき、x∈Zの同値類C(x)は
C(x)={y∈Z|x∼y}={y∈Z|x≡y (mod m)}
となります。
そもそも定理2.から、この関係∼の同値類はZを交わらない和集合でもって分割することができます。
これが、この章の最初に述べた「クラス分けできる」という意味です。
では、この同値類C(x)の正体は何でしょうか？
先述した通り、a≡b (mod m)は
でした。
故に、C(x)={y∈Z|x≡y (mod m)}は
ということになります。
合同類の例
整数の合同≡の同値類は、合同類やら剰余類とも呼ばれます。
例1.m=2のとき
答えから言えば、m=2の剰余類は
C2(0)={x∈Z|x≡0 (mod 2)}C2(1)={y∈Z|y≡1 (mod 2)}
の2つしか存在しません。
なぜなら、整数を2で割った余りは0か1かのいずれかの場合しか無いからです。
もっと言えば、a≡b (mod m)は「aをmで割った余りとbをmで割った余りが一致する」という意味ですから、上記の2種類しか存在しません。
しかも、C0∩C1=∅です(簡単に確かめられます)。
この場合を平たく言えば、整数を偶数と奇数で分けている、ということになります。
例2.m=5のとき
これも
C5(0)={x∈Z|x≡0 (mod 5)}C5(1)={y∈Z|y≡1 (mod 5)}C5(2)={z∈Z|z≡2 (mod 5)}C5(3)={w∈Z|w≡3 (mod 5)}C5(4)={u∈Z|u≡4 (mod 5)}
の5種類しか存在しません。
実は、剰余類は適切に演算を定めれば群となります。
整数をmで割った余りをr (0≤r<|m|)と書き、その整数が含まれる剰余類をCm(r)と書きます。
すなわち、
Cm(r)={n∈Z|n≡r (mod m)}
とします。
このとき、
Z=|m|∐r=0Cm(r)
ということがわかります。
ただし、∐は交わらない和集合(共通部分が空集合であるような集合の和集合)を表わします。
ここで、
Z/mZ={Cm(0), Cm(1),⋯, Cm(m−1)}
とし、Z/mZ上に演算∗を
(∀r1,r2∈{0,1,⋯,m−1})Cm(r1)∗Cm(r2)=Cm(r1+r2)
と定めます。
ただし、r1+r2がm以上となる場合は
r1+r2≡c (mod m)
となる0≤c<|m|でもってCm(r1)∗Cm(r2)=Cm(c)で定めます。
この演算により、Z/mZは群となります。
この群を剰余群と言ったのでした。
詳しくは、【代数学の基礎シリーズ】群論編 その4を御覧ください。
皆様のコメントを下さい！
この記事を書いているのは2023/3/14です。
厳密には2023/3/15の深夜なんですが…
3月14日ということで、この日を巷では「円周率の日」と読んでいるようです。
円周率が関係する数式で筆者が最も驚いたのは
1π=2√2992∞∑n=0(4n)!(1103+26390n)(4n⋅99n⋅n!)4
です。
この式は、「インドの魔術師」と称されたインド出身の数学者シュリニヴァーサ・ラマヌジャンが発見した式です。
「なんじゃこれは」というのが第一印象でした。
皆さんが印象に残っている数式をコメントで教えて下さい！
結
今回は、合同式について厳密に解説しました。
合同式a≡b (mod m)のmは自然数として定められることが多いですが、実は0でない整数であれば何でも良いのです。
そして、整数の合同≡は同値関係であり、Zを有限個のグループに分けることができるのでした。
次回は、合同式の性質として、実質的に=と同様に扱えるということについて解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかる∂かもしれませんが…)
初等整数論について、以下の書籍をオススメします！
コメントをする