合同式（mod）の成り立ち〜well-definedの意味を考える〜

数学という学問には「分類定理」と総称される問題があり、「対象を分類したい！」というひとつの大きなテーマがあります。

今回は「分類すること」をテーマとし、高校数学の数学Aにおいて発展的内容として位置付けられる「合同式」を扱いたいと思います。

余りなどを計算するときに非常に便利な合同式ですが、何故こんなに便利なのか、どうして直感的に使うことが可能なのか、そのあたりを数学的に明らかにしたいと思います。

キーワードは「同値関係」と「well-defined」です。

“良い” 関係とは何か？
1. 同値関係の定義
2. 例
関係を持つ仲間たちを同一視する
1. 同値関係と代表元の定義
2. 例
加減乗法がwell-definedであること
合同式の誕生！
最後に

“良い” 関係とは何か？

同値関係の定義

分類するということは、学校のある学年を例に挙げれば、クラス分けをするようなイメージです。クラス分けをすると、クラスメイトたちは「担任の先生が同じ」という関係を持ちます。（先生は複数のクラスを担任しないものとします。）

このように、要素たちを分類できれば、それらは関係を持ちます。逆に、要素たちに “良い” 関係を定めることができれば、それを元に要素を分類することができるというわけです。

その “良い” 関係における、「良い」とはどのような性質を指すのでしょうか。以下で定義をしたいと思います。

$X$ を空でない集合として、$X$ の元を分類することを考えます。（「元」とは集合の要素のことです。）

$X$ の元 $x,y$ に対して、「$x$ が $y$ と関係を持つ」ことを
$$
x\sim y
$$と書くことにします。

このとき、任意の元 $x,y,z\in X$ に対して、以下の性質を考えます。

$x\sim x$ である。（反射律）
$x\sim y$ ならば $y\sim x$ となる。（対称律）
$x\sim y$ かつ $y\sim z$ ならば $x\sim z$ となる。（推移律）

これらを満たす関係 $\sim$ が、先ほど述べた “良い” 関係で、数学の用語で $X$ 上の「同値関係」（どうちかんけい）と呼ばれます。

また、$x\sim y$ であることを、$x$ と $y$ は同値であるといいます。

この定義は抽象的ですので、いくつかの例を見ようと思います。

例

説明に使ったように、$X=(\mbox{学校のある学年})$ として、関係を
$$
x\sim y\ \Longleftrightarrow\ x\ \mbox{は}\ y\ \mbox{と担任の先生が同じ}
$$と定義します。このとき、

$x$ は $x$ 自身と担任の先生が同じ（反射律が成り立つ）
$x$ は $y$ と担任の先生が同じならば、$y$ は $x$ と担任の先生が同じ（対称律が成り立つ）
$x$ は $y$ と担任の先生が同じで、$y$ は $z$ と担任の先生が同じならば、$x$ は $z$ と担任の先生が同じ（推移律が成り立つ）

となるので、この関係は $X$ 上の同値関係となります。

他にも同値関係となる例を挙げていきます。

$X=(\mbox{整数全体})$ とする。$n$ を正の整数として固定し
$$
x\sim y\ \Longleftrightarrow\ x-y\ \mbox{は}\ n\ \mbox{の倍数}
$$と定義すると、この関係は $X$ 上の同値関係。（この同値関係は後で再登場します。）
$X=(\mbox{三角形全体})$ とする。
$$
x\sim y\ \Longleftrightarrow\ x\ \mbox{は}\ y\ \mbox{と合同}
$$と定義すると、この関係は $X$ 上の同値関係。
$X=(\mbox{三角形全体})$ とする。
$$
x\sim y\ \Longleftrightarrow\ x\ \mbox{は}\ y\ \mbox{と相似}
$$と定義すると、この関係は $X$ 上の同値関係。

一方で、同値関係とならない関係もあります。

$X=(\mbox{非負整数全体})$ とする。
$$
x\sim y\ \Longleftrightarrow\ x>0\ \mbox{かつ}\ y>0\ \mbox{かつ}\ x=y
$$と定義すると、この関係は対称律と推移律を満たすが、反射律を満たさない。（反例 $x=0$）
$X=(\mbox{実数全体})$ とする。
$$
x\sim y\ \Longleftrightarrow\ x \leq y
$$と定義すると、この関係は反射律と推移律を満たすが、対称律を満たさない。（反例 $x=0$, $y=1$）
$X=(\mbox{学校のあるクラス})$ とする。
$$
x\sim y\ \Longleftrightarrow\ x\ \mbox{は}\ y\ \mbox{と同じ部活に所属している}
$$と定義すると、この関係は反射律と対称律を満たすが、推移律を満たさない。（反例 $x$ が陸上競技部, $y$ が陸上競技部と吹奏楽部, $z$ が吹奏楽部）

様々な関係があるということを感じていただけましたでしょうか？

みなさんも適当な集合 $X$ と、その上の関係 $\sim$ を考えてみて、３つの条件のどれを満たすか考えてみると、良い頭の体操になるかと思います。

これより先は、同値関係に限定して見てゆきます。

関係を持つ仲間たちを同一視する

同値関係と代表元の定義

さて、同値関係 $\sim$ が定義された集合 $X$ を考えます。

$X$ の任意の元 $x$ に対して、$x$ と同値なもの全体を考え、それを $[x]$ と書きます。

集合の言葉で書けば、
$$
[x]=\{y\in X \mid y\sim x\}
$$となります。

このとき、$[x]$ を $x$ の同値類といい、$x$ をその代表元といいます。

先に挙げた学年のクラス分けの例で言うと、同値類が各クラスで、代表元がそのクラスのある生徒となります。

この例からもわかるように、「$x$ と $y$ は担任の先生が同じ $\Longleftrightarrow$ $x$ のクラスと $y$ のクラスは同じ」すなわち
$$
x \sim y\ \Longleftrightarrow\ [x]=[y]
$$が成り立ちます。

また、「学年は相異なる全てのクラスから構成される」すなわち、$[x_1], \cdots, [x_r]$ を相異なる全ての同値類とすると
$$
X=[x_1]\cup \cdots\cup [x_r]
$$が成り立ちます。

この $[x]$ という表記において、これは $x$ の属すクラスでした。（同値類は英語で “equivalence class” といいます。）

代表元 $x$ は、まさに、クラスの代表である学級委員と思っていただければ良いです。

ここで、「誰を学級委員に選出するか」という問題が出てきます。

今まで見てきた理論上は、同じクラスの人々は互いに同値ですから、誰を選んでも良いことになります。

であるならば、問題を解くときに便利に働く代表元を選びたいですよね。

例

整数全体 $X$ には、例に挙げたように同値関係
$$
x\sim y\ \Longleftrightarrow\ x-y\ \mbox{は}\ n\ \mbox{の倍数}
$$が定義できます。

簡単のために $n=3$ として、具体的に同値類と代表元を求めてみましょう。

まず、$[0]$ は

「$x-0$ が $3$ の倍数になる整数 $x$ の全体」

となりますから、すなわち、$3$ の倍数全体
\begin{align}
[0]=\{\cdots,-9,-6,-3,0,3,6,9,\cdots\}\tag{0}
\end{align}ですね。

代表元は、この中からなら何を選んでも良い（つまり、$\cdots=[-6]=[-3]=[0]=[3]=[6]=\cdots$ である）ので、ここでは “ $0$ ” を選びましょう。

次に、$[1]$ は

「$x-1$ が $3$ の倍数になる整数 $x$ の全体」

となりますから、すなわち、$3$ で割った余りが $1$ である整数全体
\begin{align}
[1]=\{\cdots,-8,-5,-2,1,4,7,10,\cdots\}\tag{1}
\end{align}ですね。

ここでも代表元は何を選んでも良いので、ここでは “ $1$ ” を選びましょう。

最後に、$[2]$ は

「$x-2$ が $3$ の倍数になる整数 $x$ の全体」

となりますから、すなわち、$3$ で割った余りが $2$ である整数全体
\begin{align}
[2]=\{\cdots,-7,-4,-1,2,5,8,11,\cdots\}\tag{2}
\end{align}ですね。

もちろん代表元は何を選んでも良いので、ここでは “ $2$ ” を選びましょう。

以上、(0)、(1)、(2)より、整数全体の集合を改めて $\mathbb{Z}$ と書くことにすれば
$$
\mathbb{Z}=[0]\cup [1]\cup [2]
$$と書くことができますね。これが、整数の分類になっているわけです。

この同値関係において、同値類の代表元は $3$ で割った余りの $0,1,2$ からとれていますよね。

このことから、整数全体 $\mathbb{Z}$ にこの同値関係を定めたときの同値類を「剰余類」（じょうよるい）と呼ばれます。

また、同値であることを「合同」であるといいます。

ここまでがキーワードのひとつめ「同値関係」の話題でした。

これより先は整数全体 $\mathbb{Z}$ に話題を限定して、ふたつめのキーワード「well-defined」について見てゆきます。

加減乗法がwell-definedであること

上で見たように、$\mathbb{Z}$ には合同と呼ばれる同値関係
$$
a\sim b\ \Longleftrightarrow\ a-b\ \mbox{は}\ n\ \mbox{の倍数}
$$が定義されていました。

以下、簡単のために $n=7$ としましょう。

上で $n=3$ として見たように、整数全体 $\mathbb{Z}$ は剰余類によって
$$
\mathbb{Z}=[0]\cup [1]\cup [2]\cup [3]\cup [4]\cup [5]\cup [6]
$$と分解できていました。

ここで、剰余類の集合を $\mathbb{Z}/7\mathbb{Z}$ と書くことにします。つまり
$$
\mathbb{Z}/7\mathbb{Z}=\{[0], [1], [2], [3], [4], [5], [6]\}
$$です。

ここでの目標は、この「括弧付きの整数」からなる剰余類の集合 $\mathbb{Z}/7\mathbb{Z}$ に演算を定めることです。

その演算とは、突飛なものではなく、整数全体 $\mathbb{Z}$ に定義されていた加法・減法・乗法を元に遺伝させることができないかを考えます。

自然に考えれば、

$[1]+[2]$ は何かと問われたとき、$[3]$ と答えたいですよね！

$[4]-[6]$ は何かと問われたとき、$[-2]$ すなわち $[5]$ と答えたいですよね！！

$[3]\times[5]$ は何かと問われたとき、$[15]$ すなわち $[1]$ と答えたいですよね！！！

それでいいんです。それでいいんですが、怪しい点、確かめておくべき点があるのです。お気付きになるでしょうか？

先に述べたように、代表元のとり方は自由です。

自由なのに、勝手に $1$ と $2$ を使って $[1]+[2]=[1+2]=[3]$ としても良いのでしょうか。

代表元として、別に $8$ と $16$ を使って足してみても同じ答え $[3]$ になりますか？

「如何なる代表元のとり方をしても、

答えは同じものに定まりますか？」

これを確かめないと、代表元のとり方によって答えが自由に変わる、トンデモ演算が出来上がってしまいますよね。

「如何なる代表元のとり方をしても、

演算結果は同じものに定まること」

を、その演算は「well-defined」であるといいます。これがキーワードのふたつめです。

以下、これを確認してゆきましょう。

加法について

加法がwell-definedであることを証明しましょう。

具体的には、“複数の代表元のとり方をしても、答えは等しい” ことを言えば良いのですから

$[a]=[a^\prime]$ かつ $[b]=[b^\prime]$

ならば

$[a+b]=[a^\prime+b^\prime]$

を示すことになります。早速、示しましょう。

– – – – – 証明 – – – – –

$[a]=[a^\prime]$ かつ $[b]=[b^\prime]$ より $a-a^\prime$ と $b-b^\prime$ は共に $7$ の倍数である。よって、
$$
(a+b)-(a^\prime +b^\prime )=(a-a^\prime )+(b-b^\prime )
$$ も $7$ の倍数となる。これより、
$$
[a+b]=[a^\prime +b^\prime ]
$$ を得る。

– – – – – 証明終 – – – – –

減法について

減法がwell-definedであることを証明するには、加法と同様に

$[a]=[a^\prime]$ かつ $[b]=[b^\prime]$

ならば

$[a-b]=[a^\prime-b^\prime]$

を示せば良いのですが、加法の場合とほぼ同じなので、証明は省略したいと思います。（手を動かして再現してみましょう。）

乗法について

乗法がwell-definedであることもまた、同様です。少しだけ計算に工夫があるので、一応書いておきますね。

$[a]=[a^\prime]$ かつ $[b]=[b^\prime]$

ならば

$[ab]=[a^\prime b^\prime]$

を示します。

– – – – – 証明 – – – – –

$[a]=[a^\prime]$ かつ $[b]=[b^\prime]$ より $a-a^\prime$ と $b-b^\prime$ は共に $7$ の倍数である。よって、
$$
ab-a^\prime b^\prime =a(b-b^\prime )+(a-a^\prime )b^\prime
$$ も $7$ の倍数となる。これより、
$$
[ab]=[a^\prime b^\prime ]
$$ を得る。

– – – – – 証明終 – – – – –