剰余演算と剰余環
Abstract
整数の剰余演算と, 整数の剰余類に関してまとめる.
Explanation
剰余演算
除法の原理
剰余演算を定義する前に, 割り算の商と剰余が一意的であるという事実を再確認しておく.
Fact (除法の原理)「原理」と呼ばれることが多いが, 実は, 整列可能定理から示せる「定理」である.
整数$ n \in \Zと正整数$ m \in \Z_{> 0}に対し,
$ n = qm + r \pod{0 \le r < m}
を満たす整数$ q, r \in \Zが一意的に存在する. $ nを被除数 (dividend), $ mを法 (modulus)と呼び, $ q, rをそれぞれ, $ nを$ mで割った商 (quotient), 剰余 (remainder / residue) と呼ぶ.
なお, 法を正整数$ m > 0に限っているが, 負整数$ m < 0で割る場合は$ -nを正整数$ |m|で割れば良い.
剰余演算の定義
さて, 除法の原理より整数$ nと法$ m > 0に対して剰余が一意的に定まるので, 次の剰余演算の定義はきちんと意味を持つ.
Definition (剰余演算)
整数$ n \in \Zと法$ m \in \Z_{>0}に対し, $ nを$ mで割った剰余を$ n \bmod mで表す.
整数の合同関係
定義と性質
整数の集合$ \Zに対して, 剰余演算$ \bmodによる次の二項関係 (binary relation) を定義する.
Definition (整数の合同)つまり, $ mで割った剰余が等しい整数を合同としている.
正整数$ m \in \Z_{> 0}に対し, 整数$ a, bが$ mを法として合同 (congruent modulo $ m) とは, $ a \bmod m = b \bmod mとなることをいい, $ a \equiv b \pmod{m}で表す.
Remark
$ m = 1のときは常に$ a \bmod m = 0となり面白くないので, 普通は$ m \ge 2で考えることが多い.
$ a \equiv b \pmod{m}のとき, $ r = a \bmod m = b \bmod mとおくと, 整数$ k, l \in \Zを使って$ a = km + r, ~ b = lm + rと表せることに注意する. これより, $ a = b + (k - l)mとなるので, 整数$ n \in \Zを用いて$ a = b + nmと表せる.
このように定めた二項関係は同値関係 (equivalent relation) になっている. さらに, 合同関係 (congruence relation) となっており, 整数$ \Zに定められている加法$ +と乗法$ \cdotの両方と両立する.
Proposition 1
任意の$ m \in \Z_{> 0}に対し, 上で定めた二項関係$ \equivは, 整数環$ (\Z, +, \cdot)上の合同関係である. すなわち, 次が成立する:(1)〜(3)より, $ \equivは同値関係になる.
(1) (反射律) 任意の$ a \in \Zに対し, $ a \equiv a \pmod{m}.
(2) (対称律) 任意の$ a, b \in \Zに対し, $ a \equiv b \pmod{m} \implies b \equiv a \pmod{m}.
(3) (推移律) 任意の$ a, b, c \in \Zに対し, $ a \equiv b \pmod{m}かつ$ b \equiv c \pmod{m} \implies a \equiv c \pmod{m}.
(4) (演算との両立) 任意の$ a, b, c, d \in \Zに対し, $ a \equiv b \pmod{m}かつ$ c \equiv d \pmod{m}のとき,
(4-1) $ a + c \equiv b + d \pmod{m}が成立する.
(4-2) $ a \cdot c \equiv b \cdot d \pmod{m}が成立する.
Proof
(1)〜(3) は, $ =の反射性・対称性・推移性より成立する.
(4) $ a \equiv b \pmod{m}かつ$ c \equiv d \pmod{m}のとき, 整数$ k, l \in \Zを用いて$ a = b + km, ~ c = d + lmと表せる (上のRemark参照). これより, $ a + c = b + d + (k + l)m, $ a \cdot c = b \cdot d + (bl + dk + klm)mが成立する. $ k + l, bl + dk + klm \in \Zであるから, $ a + c \equiv b + d \pmod{m}, ~ a \cdot c \equiv b \cdot d \pmod{m}が成立する.$ \blacksquare
上の(4)を利用することで, 以下の性質が系として得られる.
Corollary 2
任意の正整数$ m \in \Z_{> 0}に対し, 次が成立する:
$ i = 1, \dots, nに対して, 整数$ a_i, b_i \in \Zが $ a_i \equiv b_i \pmod{m}を満たすとき,
(1) $ \sum_{i = 1}^{n} a_i \equiv \sum_{i = 1}^{n} b_i \pmod{m},
(2) $ \prod_{i = 1}^{n} a_i \equiv \prod_{i = 1}^{n} b_i \pmod{m}.
Corollary 3
任意の正整数$ m \in \Z_{> 0}に対し, 次が成立する:
整数$ a, b \in \Zが $ a \equiv b \pmod{m}を満たすとき, 任意の整数$ c \in \Zと任意の非負整数$ n \in \Z_{\ge 0}に対して,
(1) $ a \pm c \equiv b \pm c \pmod{m},
(2) $ a \cdot c \equiv b \cdot c \pmod{m},
(3) $ a^n \equiv b^n \pmod{m}.
整数の剰余類別
剰余類と商集合
上で定義された合同関係$ \equivによって, 整数の集合$ \Zを類別していく.
Definition (剰余類)
$ m \in \Z_{> 0}を正整数とする. 整数$ a \in \Zに対し, 法$ mに関する$ aの合同類 (congruence class) あるいは剰余類 (residue class) を
$ a + m \Z := \{ n \in \Z \mid n \equiv a \pmod{m} \}
と定義する. また, $ aを剰余類$ a + m \Zの代表元 (representative) と呼ぶ. $ mが文脈上明らかなとき, $ \overline{a} = a + m \Zと略記することがある. 写像$ \overline{\,\cdot\,} \colon a \mapsto \overline{a}を, $ \Z / m \Zへの射影 (projection) という.
$ \Zのすべての剰余類を集めた集合を$ \Z / m \Z := \{ a + m \Z \mid a \in \Z \}と書き, 合同関係$ \equivによる商集合 (quotient set) という.
Remark
$ n \equiv a \pmod{m}とは, 「$ nと$ aの$ mによる剰余は等しい」ということである. つまり, $ a + m \Zとは$ mによる剰余が$ aと等しい整数からなる集合である.
とくに, $ a = 0のときは$ 0 + m \Zの代わりに$ m \Zと書かれる. $ m \Zは$ mの倍数からなる集合である.
$ n \equiv a \pmod{m} \iff \exists k \in \Z, n = a + mkであったので, $ a + m \Zをもう少し書き下してみると, $ a + m \Z = \{ n \in \Z \mid \exists k \in \Z, n = a + mk \} = \{ a + N \mid N \in m \Z \}となる.
「$ aに$ mの倍数を足した形の整数からなる集合だ」という情報が$ a + m \Zという表記にあらわれている. より詳しく言えば, $ m\Zが環$ \Zのイデアルであることを意識した表記である.
整数$ a, b \in \Zに対して, 表記上$ a + m \Z, b + m \Zと異なっていたとしても実際は$ S = a + m \Z = b + m \Zとなって重複していることがある. この場合, 集合$ Sを考えるときは, $ aと$ bのいずれを代表元に選んでもよい. このように, 代表元の選び方には任意性がある.
$ \Z / m \Zへの射影は全射である.
一般に, 同値関係$ \simによる集合$ Xの商集合は$ X / {\sim}と書く. ここでも, $ \Z / m \Zの代わりに$ \Z / {\equiv}と書いても良いのだが, あまり一般的ではない. (法が$ mであるということが明示的にわからないのが主な理由だろう.)
二項関係$ \equivは同値関係であったから, 任意の整数$ a, b \in \Zに対して$ a + m \Z = b + m \Zまたは$ a + m \Z \cap b + m \Z = \varnothingのいずれか一方が成立する.「整数$ a, b \in \Zの$ mによる剰余は, 等しいか異なるかのいずれかである」ということを述べているに過ぎない.
Proposition 4
$ m \in \Z_{> 0}を正整数とする. 整数$ a, b \in \Zに対し, 以下は同値:
(1) $ a \equiv b \pmod{m}.
(2) $ a + m \Z = b + m \Z.
(3) $ a + m \Z \cap b + m \Z \neq \varnothing.
Proof
(1)$ \Rightarrow(2)であること.
$ n \in a + m \Zとすると, ある整数$ k \in \Zを用いて$ n = a + mkと表せる. $ a \equiv b \pmod{m}であるから, ある整数$ l \in \Zを用いて$ a = b + mlと表わせ, これらより$ n = b + m(k + l) \in b + m \Zがわかる. よって, $ a + m \Z \subseteq b + m \Z. 同様に, $ b + m \Z \subseteq a + m \Zも示せるので, $ a + m \Z = b + m \Z.
(2)$ \Rightarrow(3)であることは自明.
(3)$ \Rightarrow(1)であること
$ c \in a + m \Z \cap b + m \Zを任意にとる. $ c \in a + m \Zより$ c \equiv a \pmod{m}であり, $ c \in b + m \Zより$ c \equiv b \pmod{m}である. よって, 同値関係の対称律と推移律を利用すると, $ a \equiv b \pmod{m}. $ \blacksquare
Remark
否定を取ることで, $ a \not \equiv b \pmod{m} \iff a + m \Z \cap b + m \Z = \varnothingも成立していることもわかる.
さて, $ a + m \Zは「$ mによる剰余が$ aと等しい整数の集合」であった. $ mによる剰余は$ 0, 1, \dots, m - 1のいずれかであるから, これらを剰余類の代表元と考えると, Proposition 4より商集合の表示を具体的に与えることができる.
Corollary 5 (商集合$ \Z / m \Zの表示)
$ m \in \Z_{> 0}を正整数とすると, 同値関係$ \equivによる商集合$ \Z / m\Zは
$ \Z / m\Z = \{ m\Z, 1 + m \Z, \dots, m - 1 + m \Z \}
と表示できる.
さらに, Proposition 4より$ \Z / m\Zが$ \Zの分割を与えることもわかる.
Corollary 6 (整数の剰余類別)
$ m \in \Z_{> 0}を正整数とすると, 同値関係$ \equivによる商集合$ \Z / m\Z = \{ m\Z, 1 + m \Z, \dots, m - 1 + m \Z \}は$ \Zの分割である, i.e.,
$ \Z = \bigsqcup_{i = 0}^{m-1} (i + m \Z)
が成立する ($ \sqcupは非交和を表す).
こうして, 整数全体を$ mによる剰余で$ m個の互いに素な集合に分類することができた.
剰余環
商集合上の演算上では, 商集合の要素が集合であることを強調して$ a + m \Zと表記していたが, これを以下では数のように扱うことを強調して$ \overline{a}と表記することにした.
商集合$ \Z / m \Zを考えることで, 「整数の$ mによる剰余」のみに着目できるようになる. ただし, 商集合$ \Z / m \Zの各要素$ \overline{a} = a + m \Zは, 今のところはただの集合であり, (整数である剰余のように) 四則演算ができるものではない. そこで, $ \Zの加法$ +と乗法$ \cdotをもとにして, 商集合$ \Z / m \Zにも加法と乗法を定めることで, 各要素$ \overline{a}を数のように扱えるようにしよう.
単純には, 次のような演算の定義が考えられる: 演算の記号は統一しているが, $ \Z / m \Zでの演算は$ \Zでの演算により定義されている. つまり, 演算子$ +, \cdotの記法としては同一だが, $ :=の左辺では$ \Z / m \Zでの, 右辺では$ \Zでの演算を表しており, 別物である. これは, 演算子のオーバーロードをしているとも言えるだろう.
加法: $ \overline{a} + \overline{b} := \overline{a + b}
乗法: $ \overline{a} \cdot \overline{b} := \overline{a \cdot b}
この定義は, 剰余類$ \overline{a}, \overline{b}の代表元をそれぞれ$ a, bに選んでいることを前提とした定義になっていることに注意する. 上で述べたとおり, 剰余類$ \overline{a}, \overline{b}の代表元の選び方には任意性があった. 例えば, $ a' \equiv a \pmod{m}, ~ b' \equiv b \pmod{m}となる$ a', b' \in \Zを剰余類$ \overline{a}, \overline{b}の代表元に選んでもよい. もし仮に,
$ \overline{a + b} \neq \overline{a' + b'} — (★)
となるようなことがあったとする. $ \overline{a} = \overline{a'}, ~ \overline{b} = \overline{b'}であったから, 代表元の選び方によって$ \overline{a} + \overline{b}の演算結果が変わってしまうことになる. これでは, 演算の定義としては不都合である.
実は, 演算はwell-definedである, すなわち, 先の演算の定義では (★) のような状況は発生せず, 演算結果が代表元の選び方によらない, ということが示せる. これは, 同値関係$ \equivが合同関係になっており, Proposition 1 (4) が成立することから直ちに従う.
Lemma 7 (演算のwell-defined性)
$ m \in \Z_{> 0}を正整数とする. 商集合$ \Z / m \Zの加法$ +と乗法$ \cdotを次で定める.
加法: $ \overline{a} + \overline{b} := \overline{a + b}
乗法: $ \overline{a} \cdot \overline{b} := \overline{a \cdot b}
この演算は, well-definedである.
Proof
示すべきことは, $ \overline{a} = \overline{a'}, ~ \overline{b} = \overline{b'} \implies \overline{a + b} = \overline{a' + b'}, ~ \overline{a \cdot b} = \overline{a' \cdot b'}である.
$ \overline{a} = \overline{a'}, ~ \overline{b} = \overline{b'} \iff a \equiv a' \pmod{m}, ~ b \equiv b' \pmod{m}であるから, これはProposition 1 (4) を言い換えただけである. $ \blacksquare
商集合$ \Z / m \Zに演算が導入されたことで, $ \Z / m \Zの要素を数のように扱えるようになった. またLemma 7より, 剰余類$ \overline{a}, \overline{b}の代表元に, それぞれの剰余類に含まれるどの整数を採用したとしても, うまく演算できることがわかった.
$ \Z / m \Zの演算の定義には$ \Zの演算を利用しているため, 結合法則・分配法則・可換性などの$ \Zの演算の性質がそのまま$ \Z / m \Zでも成立する. よって, $ \Z / m \Zには演算$ +, \cdotにより環の構造がはいる.
Definition (剰余環)
$ m \in \Z_{> 0}を正整数とする. 商集合$ \Z / m \Zの加法$ +と乗法$ \cdotを次で定める.
加法: $ \overline{a} + \overline{b} := \overline{a + b}
乗法: $ \overline{a} \cdot \overline{b} := \overline{a \cdot b}
この演算により$ (\Z / m \Z, +, \cdot)は可換環になり, これを剰余環 (residue ring) と呼ぶ. 文脈上演算が明らかな場合は, 「剰余環$ (\Z / m \Z, +, \cdot)」と書く代わりに「剰余環$ \Z / m \Z」と書く.
剰余環$ \Z / m \Zにおいて, $ \overline{0} \in \Z / m \Zは加法の単位元である, i.e., 任意の$ \overline{a} \in \Z / m \Zに対して
$ \overline{a} + \overline{0} = \overline{0} + \overline{a} = \overline{a}
が成立する. また, 剰余環$ \Z / m \Zにおける$ \overline{a} \in \Z / m \Zの加法の逆元は$ \overline{- a}である, i.e.,
$ \overline{a} + \overline{-a} = \overline{-a} + \overline{a} = \overline{0}
が成立する. これにより, $ \Z / m \Zには ($ \Z / m \Zの加法$ +を利用して) 減法$ -が定義できる:
減法: $ \overline{a} - \overline{b} := \overline{a} + (- \overline{b}) = \overline{a - b}
以上より, 剰余環$ \Z / m \Zにおいては加法・減法・乗法の三つの演算がいつでも定義できることがわかった.
さらに, $ \overline{1} \in \Z / m \Zは乗法の単位元である, i.e., 任意の$ \overline{a} \in \Z / m \Zに対して
$ \overline{a} \cdot \overline{1} = \overline{1} \cdot \overline{a} = \overline{a}
が成立する.
乗法の逆元
一般に, 加法$ +の逆演算である減法$ -は, 加法の逆元を用いて定義できる. 同様に, 乗法$ \cdotの逆演算である除法$ \divは, 乗法の逆元 (逆数) を利用することで定義できる. 剰余環$ \Z / m \Zにおいては, 加法の逆元が必ず存在するので, 減法はいつでも定義できた. 一方で, 乗法$ \cdotの逆元がいつも存在するとは限らない, i.e., $ \overline{a} \in \Z / m \Zに対して,
$ \overline{a} \cdot \overline{b} = \overline{b} \cdot \overline{a} = \overline{1}
となる$ \overline{b} \in \Z / m \Zが存在しないことがある. このため, 除法をいつでも定義できるとは限らない.そもそも, 剰余環$ \Z / m \Zのもととなる$ \Zでも積の逆元が存在するのは$ \pm 1のみであったから, これは別に不思議なことではない (今は$ \Zの中だけで考えているので, 逆元は$ \Zの元でないといけない).
剰余環$ \Z / m \Zにおいて, 乗法の逆元が存在する必要十分条件を示そう.
Theorem 8 (剰余環における乗法の逆元の存在条件)
$ m \in \Z_{> 0}を正整数とし, $ a \in \Zとする. 剰余環$ \Z / m \Zの元$ \overline{a} \in \Z / m \Zに乗法の逆元が存在するための必要十分条件は, $ aと$ mが互いに素であること, i.e., $ \gcd(a, m) = 1であることである.
Proof
($ \Rightarrow)
$ \overline{a}の乗法の逆元$ \overline{x}が存在するとする. $ \overline{a} \cdot \overline{x} = \overline{a \cdot x} = \overline{1}なので, Proposition 4より$ ax \equiv 1 \pmod{m}である. よって, 整数$ k \in \Zで$ ax = 1 + mk, すなわち,
$ ax - mk = 1
を満たすものが存在する. $ dを$ aと$ mの公約数とすると, $ dは上の等式の左辺を割り切るから, 右辺の$ 1も割り切る. とくに, $ d \le 1であることがわかる. 一方, 最大公約数は正整数なので$ \gcd(a, m) \ge 1. ゆえに$ a, mの最大公約数は$ \gcd(a, m) = 1.
($ \Leftarrow)
$ \gcd(a, m) = 1であるとする. このとき, Bézoutの補題より$ ax + my = \gcd(a, m)の整数解$ x, y \in \Zが存在する. 等式を変形すると$ ax = 1 - myであり, $ ax \equiv 1 \pmod{m}. これは$ \overline{a}\overline{x} = \overline{1}を意味し, $ \overline{x}は$ \overline{a}の逆元となる. $ \blacksquare 剰余環$ \Z / m \Z上で演算を行う場合は,
$ mによる剰余と対応がつく点で都合が良いので, 各剰余類の代表元を$ 0, 1, \dots, m - 1ととって$ \Z / m \Z = \{ \overline{0}, \dots, \overline{m - 1} \}と表示しておくのが便利である. とくに,
$ \overline{a} \pm \overline{b} = \overline{(a \pm b) \bmod m}
$ \overline{a} \cdot \overline{b} = \overline{(a \cdot b) \bmod m}
であるから, $ \Zでの加法・減法・乗法を行ったあとに$ mによる剰余をとることで, $ \overline{a}と$ \overline{b}の演算結果の剰余類の代表元を$ 0, 1, \dots, m - 1のいずれかに取り直すことができる.
References