本記事の内容
本記事は、整数のグループ分けの手法の一つとして、合同式について解説する記事です。
本記事を読むに当たり、割り算定理について知っている必要があるため、以下の記事も合わせてご覧ください。
合同式とは？
筆者が高校生の頃は合同式は高校数学の範疇ではありませんでした(確かそうだったはず…)が、今や合同式は高校数学で学んでいる内容です。
故に、「合同式って何？」という質問にはたくさんの方が答えられると思います。
しかし、それは厳密でしょうか？
合同式ってなんでしょうか？
\(a\equiv b\ ({\rm mod}\ m)\)のような式です。
例えばどんなのがありますか？
\(5\equiv3\ ({\rm mod}\ 2)\)などですね。
では、先程の式\(a\equiv b\ ({\rm mod}\ m)\)の\(a,b,m\)の条件は何でしょう？
\(a,b\in\mathbb{Z}\)で、\(m\in\mathbb{N}\)です。
では、先程の式\(a\equiv b\ ({\rm mod}\ m)\)の\(a,b,m\)の意味は何でしょう？
\(a-b\)が\(m\)の倍数という意味です。
確かに先程の例\(5\equiv3\ ({\rm mod}\ 2)\)は\(5-3=2\times1\)で\(5-3\)は\(2\)の倍数ですね。
しかし、\(a\equiv b\ ({\rm mod}\ m)\)が「\(a-b\)が\(m\)の倍数という意味」であれば、\(5-3=(-1)\times(-2)\)と書くこともできますが、\(m\in\mathbb{N}\)だとするとこの場合は考えないのですか？
え…どうでしょう…（タスケテ…）
またまた登場！助け舟を出そう！
確かに、\(m\in\mathbb{N}\)でなければいけないのでしょうか？
「\(m\)の倍数」という文言が出現する以上、\(0\)は排除して\(m\neq0\)であるのはわかりますが、\(m>0\)でなければならないのでしょうか？
実は、\(m\in\mathbb{Z}\setminus\left\{0\right\}\)で良いのです。
合同式とは何か？(厳密な話)
確かに、高校では\(m\in\mathbb{N}\)と習ったかもしれません(筆者は高校で合同式を習っていないので定かではありませんが…)。
しかし、Aくんの指摘通り\(5-3=(-1)\times(-2)\)とも書けるため、\(m\in\mathbb{N}\)でなくとも良いのではないでしょうか。
答えは、
です。
つまり、\(m\)は\(0\)以外の整数であれば何でも良い、マイナスでも良い、ということです。
厳密に明示しましょう。
合同式
\(m\in\mathbb{Z}\setminus\left\{0\right\}\)とする。\(a,b\in\mathbb{Z}\)であり、\(a-b\)が\(m\)で割り切れる、すなわち $$ (\exists k\in\mathbb{Z})\ {\rm s.t.}\ a-b=km $$ となるとき、\(a\equiv b\ ({\rm mod}\ m)\)と書き、\(a\)と\(b\)は\(m\)を法として合同という。また、\(a\equiv b\ ({\rm mod}\ m)\)という形式の式を合同式という。mod？
\(\ ({\rm mod}\ )\)はmodulusのmod。すなわち、\(5\equiv 3\ ({\rm mod}\ -2)\)という式も成り立つ、というわけです。
合同式の間違った解釈
\(a\equiv b\ ({\rm mod}\ m)\)は
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ a-b=km
$$
が成り立つことだ、と説明しました。
ではこの式の意味は何でしょうか？
少々変形すると、
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ a=km+b
$$
となります。
「お！これ、割り算定理の形じゃん！」となるのではないでしょうか。
ここで、割り算定理(剰余の定理)とは以下でした。
定理0.(割り算定理、剰余の定理)
\(a,b\in\mathbb{Z}\)とする。\(b>0\)であるならば、 $$ a=qb+r\quad (0\leq r<\left|b\right|) $$ となるような整数\(q,r\)が\(a\in\mathbb{Z}\)に対して一意的に存在する。割り算定理(剰余の定理)の証明は【代数学の基礎シリーズ】初等整数論編 その2をご覧ください。
確かに、割り算定理と似た形をしています。
さて、同じでしょうか？
実は、似て非なるものです。
たとえば、最初に挙げた例
$$
5\equiv3\ ({\rm mod}\ 2)
$$
を見てみると、
\begin{eqnarray}
5-3=2\times1\Longleftrightarrow5=1\times2+3
\end{eqnarray}
となり、たしかに割り算定理の形をしています。
割り算定理において\(a=5\)、\(q=1\)、\(b=2\)、\(r=3\)です。
しかしながら、割り算定理は\(r\)の条件が\(0\leq r<\left|b\right|\)です。
\(r=3>2=b\)となり、この条件を満たしません。
したがって、
ということになります。
合同式の意味は？
では、\(a\equiv b\ ({\rm mod}\ m)\)の意味とは何でしょうか？
答えは次の命題です。
命題1.
\(a,b\in\mathbb{Z}\)、\(m\in\mathbb{Z}\setminus\left\{0\right\}\)とするとき、\(a\equiv b\ ({\rm mod}\ m)\)であることと、\(a\)および\(b\)を\(m\)で割った余りが等しいことは同値である。要するに、\(a\equiv b\ ({\rm mod}\ m)\)が成り立つと言われたらば、「\(a\)を\(m\)で割った余りと\(b\)を\(m\)で割った余りが等しいってことだ」というわけです。
命題1.の証明
割り算定理(剰余の定理)から、
$$
a=qm+r,\quad b=q^\prime m+r^\prime
$$
と書くことができます。
ただし、\(q,r,q^\prime,r^\prime\in\mathbb{Z}\)であり、\(0\leq r<\left|m\right|\)かつ\(0\leq r^\prime<\left|m\right|\)です。
①\(a\equiv b\ ({\rm mod}\ m)\Longrightarrow a\)および\(b\)を\(m\)で割った余りが等しいことの証明
\(a\equiv b\ ({\rm mod}\ m)\)であれば、
$$
(\exists c\in\mathbb{Z})\ {\rm s.t.}\ a-b=mc
$$
です。
今、
\begin{eqnarray}
a-b&=&qm+r-\left( q^\prime m+r^\prime\right)\\
&=&m\left( q-q^\prime\right)+r-r^\prime
\end{eqnarray}
であるため、\(a\equiv b\ ({\rm mod}\ m)\)であれば、
$$
(\exists c\in\mathbb{Z})\ {\rm s.t.}\ m\left( q-q^\prime\right)+r-r^\prime=mc\tag{\(\ast\)}
$$
ということになります。
故に、\((\ast)\)を変形して
$$
r-r^\prime=m\left( c+q^\prime-q\right)
$$
です。
仮に、\(r\neq r^\prime\)、すなわち\(r-r^\prime\neq0\)だとします。
\(m\in\mathbb{Z}\setminus\left\{0\right\}\)により\(m\neq0\)ですから、このとき\(c+q^\prime-q\neq0\)となります。
\(c,q^\prime,q\in\mathbb{Z}\)により、\(c+q^\prime-q\in\mathbb{Z}\)です。
そして\(c+q^\prime-q\neq0\)であるから、\(c+q^\prime-q\geq1\)または\(c+q^\prime-q\leq-1\)です。
したがって、\(\left|c+q^\prime-q\right|\geq1\)となります。
故に、
$$
\left|m(c+q^\prime-q)\right|\geq\left|m\right|
$$
となります。
しかしながら、\(0\leq r<\left|m\right|\)かつ\(0\leq r^\prime<\left|m\right|\)であったため、\(-\left|m\right|<r-r^\prime<\left|m\right|\)です。
すなわち、
$$
\left|r-r^\prime\right|<\left|m\right|
$$
です。
故に、\(r-r^\prime=m\left( c+q^\prime-q\right)\)に矛盾です。
したがって、\(r=r^\prime\)です。
②\(a\)および\(b\)を\(m\)で割った余りが等しい\(\Longrightarrow a\equiv b\ ({\rm mod}\ m)\)の証明
逆に、\(r=r^\prime\)であれば、\(a-b=m(q-q^\prime)\)となるため、\(a\equiv b\ ({\rm mod}\ m)\)です。
命題1.の証明終わり
整数の合同は\(\mathbb{Z}\)をクラス分けします。
\(\mathbb{Z}\)は言わずもがな無限集合(要素が無限個の集合)です。
要素の個数が有限でないことの恩恵もありますが、無限個のものの特徴を捉えるのは難しいものです。
実は、整数の合同は\(\mathbb{Z}\)を有限個のクラス(グループと言っても良いでしょう)に分けることができます。
「クラス分け？お？もしかしてアレか？」となった方、鋭いです。
その通り、整数の合同\(\equiv\)は同値関係なのです。
同値関係と同値類の軽い復習
同値関係
一般に、次の３条件を満たす集合\(X\)上の関係\(\sim\)を同値関係(equivalence relation)という。- \(x\in X\)のとき、\(x\sim x\)(反射律),
- \(x,y\in X\)のとき、\(x\sim y\Rightarrow y\sim x\)(対称律),
- \(x,y,z\in X\)のとき、\(x\sim y,\ y\sim z\Rightarrow x\sim z\)(推移律)
定理2.
\(x\in X\)と同値な要素全体を\(C_x\)と書き、これを\(x\)の同値類(equivalence class)という。すなわち、 $$C_x=\{y\in X\mid x\sim y\}$$ である。 このとき、次が成り立つ。- \(x\in C_x\),
- \(C_x\cap C_y\neq \emptyset \Rightarrow C_x=C_y\),
- \(C_x\neq C_y\Rightarrow C_x\cap C_y= \emptyset\).
詳しくは、【論理と集合シリーズ】その7を御覧ください。
そもそも整数の合同\(\equiv\)は二項関係なのか？
二項関係です。
実際、
$$
R_m=\left\{(x,y)\in\mathbb{Z}\middle|(\exists k\in\mathbb{Z})\ {\rm s.t.}\ x-y=mk\right\}
$$
としたとき、\((a,b)\in R_m\)を\(a\equiv b\ ({\rm mod}\ m)\)と書いている、と捉えることができるからです。
整数の合同\(\equiv\)は同値関係なのか？
同値関係です。
命題3.
整数の合同\(\equiv\)は同値関係である。すなわち、任意の\(a,b\in\mathbb{Z}\)、任意の\(m\in\mathbb{Z}\setminus\left\{0\right\}\)に対して- 反射律 \(a\equiv a\ ({\rm mod}\ m)\)
- 対称律 \(a\equiv b\ ({\rm mod}\ m)\Longrightarrow b\equiv a\ ({\rm mod}\ m)\)
- 推移律 \(a\equiv b\ ({\rm mod}\ m)\ \land\ b\equiv c\ ({\rm mod}\ m)\Longrightarrow a\equiv c\ ({\rm mod}\ m)\)
命題3.の証明
①反射律の証明
\(a-a=0=0\times m\)により、\(a\equiv a\ ({\rm mod}\ m)\)です。
②対称律の証明
\(a\equiv b\ ({\rm mod}\ m)\)とすると、
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ a-b=mk
$$
です。
このとき、
$$
b-a=m\times (-k)
$$
であり、当然\(-k\in\mathbb{Z}\)であるため、\(b\equiv a\ ({\rm mod}\ m)\)です。
③推移律の証明
\(a\equiv b\ ({\rm mod}\ m)\)かつ\(b\equiv c\ ({\rm mod}\ m)\)とします。
すなわち、
\begin{eqnarray}
&&(\exists k_1\in\mathbb{Z})\ {\rm s.t.}\ a-b=mk_1\\
&&(\exists k_2\in\mathbb{Z})\ {\rm s.t.}\ b-c=mk_2\\
\end{eqnarray}
とします。
このとき、
\begin{eqnarray}
a-c&=&a-b+b-c\\
&=&mk_1-mk_2\\
&=&m(k_1-k_2)
\end{eqnarray}
となるため、\(a\equiv c\ ({\rm mod}\ m)\)です。
したがって、整数の合同\(\equiv\)は同値関係です。
命題3.の証明終わり
この同値関係\(\equiv\)の同値類に着目してみます。
整数の合同\(\equiv\)の同値類に着目してみます。
体裁を整えるために、
$$
a\sim b\Longleftrightarrow a\equiv b\ ({\rm mod}\ m)
$$
と書きます。
このとき、\(x\in\mathbb{Z}\)の同値類\(C(x)\)は
\begin{eqnarray}
C(x)&=&\left\{y\in\mathbb{Z}\middle|x\sim y\right\}\\
&=&\left\{y\in\mathbb{Z}\middle| x\equiv y\ ({\rm mod}\ m)\right\}
\end{eqnarray}
となります。
そもそも定理2.から、この関係\(\sim\)の同値類は\(\mathbb{Z}\)を交わらない和集合でもって分割することができます。
これが、この章の最初に述べた「クラス分けできる」という意味です。
では、この同値類\(C(x)\)の正体は何でしょうか？
先述した通り、\(a\equiv b\ ({\rm mod}\ m)\)は
でした。
故に、\(C(x)=\left\{y\in\mathbb{Z}\middle| x\equiv y\ ({\rm mod}\ m)\right\}\)は
ということになります。
合同類の例
整数の合同\(\equiv\)の同値類は、合同類やら剰余類とも呼ばれます。
例1.\(m=2\)のとき
答えから言えば、\(m=2\)の剰余類は
\begin{eqnarray}
C_2(0)&=&\left\{x\in\mathbb{Z}\middle|x\equiv0\ ({\rm mod}\ 2)\right\}\\
C_2(1)&=&\left\{y\in\mathbb{Z}\middle|y\equiv1\ ({\rm mod}\ 2)\right\}\\
\end{eqnarray}
の2つしか存在しません。
なぜなら、整数を\(2\)で割った余りは\(0\)か\(1\)かのいずれかの場合しか無いからです。
もっと言えば、\(a\equiv b\ ({\rm mod}\ m)\)は「\(a\)を\(m\)で割った余りと\(b\)を\(m\)で割った余りが一致する」という意味ですから、上記の2種類しか存在しません。
しかも、\(C_0\cap C_1=\emptyset\)です(簡単に確かめられます)。
この場合を平たく言えば、整数を偶数と奇数で分けている、ということになります。
例2.\(m=5\)のとき
これも
\begin{eqnarray}
C_5(0)&=&\left\{x\in\mathbb{Z}\middle|x\equiv0\ ({\rm mod}\ 5)\right\}\\
C_5(1)&=&\left\{y\in\mathbb{Z}\middle|y\equiv1\ ({\rm mod}\ 5)\right\}\\
C_5(2)&=&\left\{z\in\mathbb{Z}\middle|z\equiv2\ ({\rm mod}\ 5)\right\}\\
C_5(3)&=&\left\{w\in\mathbb{Z}\middle|w\equiv3\ ({\rm mod}\ 5)\right\}\\
C_5(4)&=&\left\{u\in\mathbb{Z}\middle|u\equiv4\ ({\rm mod}\ 5)\right\}\\
\end{eqnarray}
の5種類しか存在しません。
実は、剰余類は適切に演算を定めれば群となります。
整数を\(m\)で割った余りを\(r\ (0\leq r<\left|m\right|)\)と書き、その整数が含まれる剰余類を\(C_m(r)\)と書きます。
すなわち、
$$
C_m(r)=\left\{n\in\mathbb{Z}\middle| n\equiv r\ ({\rm mod}\ m)\right\}
$$
とします。
このとき、
$$
\mathbb{Z}=\coprod_{r=0}^{\left|m\right|}C_m(r)
$$
ということがわかります。
ただし、\(\displaystyle\coprod\)は交わらない和集合(共通部分が空集合であるような集合の和集合)を表わします。
ここで、
$$
\mathbb{Z}/{m\mathbb{Z}}=\left\{C_m(0),\ C_m(1),\cdots,\ C_m(m-1)\right\}
$$
とし、\(\mathbb{Z}/{m\mathbb{Z}}\)上に演算\(\ast\)を
$$
(\forall r_1,r_2\in\left\{0,1,\cdots,m-1\right\})\quad C_m(r_1)\ast C_m(r_2)=C_m(r_1+r_2)
$$
と定めます。
ただし、\(r_1+r_2\)が\(m\)以上となる場合は
$$
r_1+r_2\equiv c\ ({\rm mod}\ m)
$$
となる\(0\leq c<\left|m\right|\)でもって\(C_m(r_1)\ast C_m(r_2)=C_m(c)\)で定めます。
この演算により、\(\mathbb{Z}/{m\mathbb{Z}}\)は群となります。
この群を剰余群と言ったのでした。
詳しくは、【代数学の基礎シリーズ】群論編 その4を御覧ください。
皆様のコメントを下さい！
この記事を書いているのは2023/3/14です。
厳密には2023/3/15の深夜なんですが…
3月14日ということで、この日を巷では「円周率の日」と読んでいるようです。
円周率が関係する数式で筆者が最も驚いたのは
$$
\frac{1}{\pi}=\frac{2\sqrt{2}}{99^2}\sum_{n=0}^\infty\frac{(4n)!(1103+26390n)}{\left( 4^n\cdot 99^n\cdot n!\right)^4}
$$
です。
この式は、「インドの魔術師」と称されたインド出身の数学者シュリニヴァーサ・ラマヌジャンが発見した式です。
「なんじゃこれは」というのが第一印象でした。
皆さんが印象に残っている数式をコメントで教えて下さい！
結
今回は、合同式について厳密に解説しました。
合同式\(a\equiv b\ ({\rm mod}\ m)\)の\(m\)は自然数として定められることが多いですが、実は\(0\)でない整数であれば何でも良いのです。
そして、整数の合同\(\equiv\)は同値関係であり、\(\mathbb{Z}\)を有限個のグループに分けることができるのでした。
次回は、合同式の性質として、実質的に\(=\)と同様に扱えるということについて解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかる∂かもしれませんが…)
初等整数論について、以下の書籍をオススメします！
コメントをする