整除関係
概要
整除関係（divisibility relation）とは、可換環の元 $a,b$ について $b=ac$ となる元 $c$ が同じ環にあるとき $a\mid b$ と書く、「割り切る」という関係である。反射的かつ推移的な前順序で、$a\mid b$ は単項イデアルの包含 $(b)\subset(a)$ と同じであり、どの環で考えるかによって変わる（$\mathbb{Z}$ では $2\nmid3$、$\mathbb{Q}$ では $2\mid3$）。$0$ 以上の整数では半順序になり、$1$ が最小、$0$ が最大で、任意の部分集合が最大公約数と最小公倍数を下限・上限としてもつ完備束をなす。正の整数の整除の順序は素因数の指数の成分ごとの大小と同型で、分配束であり、$n$ の約数の順序で $1$ から $n$ への極大鎖は $\Omega(n)$ 段で多項係数の本数だけある。
整除関係（divisibility relation）は、「$a$ が $b$ を割り切る」という 2 つの数（あるいは環の元）の間の関係 $a\mid b$ のことである。1 組の数について割り切れるかどうかを問うだけでなく、関係そのものを 1 つの構造として眺めると、整数全体は大小とはまったく違う順序をもつ。$1$ が最小で $0$ が最大であり、$2$ と $3$ は比べられず、最大公約数と最小公倍数が下限と上限になる。この記事では、整除関係を可換環の上の関係として定義し、それが前順序であることと単項イデアルの包含との対応を確かめたあと、主定理として $0$ 以上の整数が整除関係について完備束をなすこと と、正の整数の整除の順序が素因数の指数の成分ごとの大小と同じ形をしていること を証明する。後者から、約数全体のなす順序の鎖の長さと本数が素因数分解だけで数えられる。
定義
$R$ を可換環とし、$a,b\in R$ とする。ある $c\in R$ が存在して
$$
b=ac
$$
となるとき、$a$ は $b$ を 割り切る（divides）といい、$a\mid b$ と書く。このとき $a$ を $b$ の 約数（約元）、$b$ を $a$ の 倍数（倍元）という。そのような $c$ が $R$ に存在しないとき $a\nmid b$ と書く。$R$ の元の組 $(a,b)$ のうち $a\mid b$ となるもの全体がなす $R$ 上の 2 項関係を、$R$ の 整除関係 という。
$R=\mathbb Z$ のときが整数の整除関係である（Sho08 §1.1、p. 1。Ste17 Definition 1.1.1、p. 2）。環 $R$ の元についての定義も同じ形であり（Sho08 §7.1.1、p. 170）、整数の場合の性質のうち足し算と掛け算だけから出るものは、そのまま一般の可換環で成り立つ。
定義から直ちに次のことがわかる。
- すべての $a$ について $a\mid 0$ である（$0=a\cdot0$）。一方 $0\mid b$ となるのは $b=0$ のときだけである（$b=0\cdot c=0$）。「$0$ で割る」ことは定義されないが、整除関係 $0\mid0$ は成り立つ。この 2 つを混同しない。
- 単元（逆元をもつ元）$u$ はすべての元を割り切る（$b=u\cdot(u^{-1}b)$）。とくに $\mathbb Z$ では $\pm1$ がすべての整数を割り切る。
- 商 $c$ が $R$ の中に あることを要求している。したがって同じ 2 つの数でも、どの環で考えるかによって割り切れるかどうかが変わる（ex-dvr-ring-dependence）。
整除関係の中で「互いに割り切る」という関係は特別な役割をもつ。
可換環 $R$ の元 $a,b$ について、ある単元 $u$ で $b=ua$ となるとき、$a$ と $b$ は 同伴（associate）であるという。
同伴な元は互いに割り切る（$b=ua$、$a=u^{-1}b$）。逆に、$R$ が整域なら互いに割り切る 2 元は同伴である（単項イデアル の記事の命題「単項イデアルの包含と整除」の 3）。$\mathbb Z$ の単元は $\pm1$ だけなので、整数 $a,b$ が互いに割り切ることは $b=\pm a$ と同じである（Sho08 Theorem 1.2、p. 2）。
直感
整除関係には 3 つの見方がある。1 つ目は 掛け算でたどり着けるか という見方で、$a\mid b$ は「$a$ に何かを掛けて $b$ を作れる」ことである。数の大小とは関係がなく、$-3\mid 12$ であり、$5\nmid 12$ である。2 つ目は 倍数の集まりの包含 で、$a\mid b$ は「$b$ の倍数はすべて $a$ の倍数」、すなわち単項イデアルについて $(b)\subset(a)$ ということである。割り切る側の方が大きな集合を生むので、向きが逆になる。3 つ目は 素因数の指数の比較 で、正の整数については $a\mid b$ は「どの素数 $p$ についても、$a$ に含まれる $p$ の個数が $b$ に含まれる $p$ の個数以下」ということである。この見方では、整除の順序は「素数ごとに 1 本ずつ用意した数直線の、成分ごとの大小」になり、$2$ と $3$ のように別の方向を向いた元どうしは比べられない。この記事の主定理は、2 つ目と 3 つ目の見方をそれぞれ正確に述べたものである。
例と反例
$3\mid 12$（$12=3\cdot4$）、$-3\mid12$（$12=(-3)(-4)$）、$12\mid -36$ であり、$5\nmid 12$、$4\nmid 14$ である。$4\nmid14$ は、有理数としての商 $14/4=7/2$ が整数でないことによる。$12$ の正の約数は $1,2,3,4,6,12$ の $6$ 個である。
$\mathbb Z$ では $2\nmid3$ である（$3=2c$ となる整数 $c$ はない）。ところが有理数体 $\mathbb Q$ では $3=2\cdot\frac32$ なので $2\mid3$ である。体では $0$ でない元はすべて単元なので、$a\neq0$ ならすべての $b$ について $a\mid b$ となり、整除関係は「$a\neq0$ または $b=0$」という情報しか持たない。分母に $2$ の冪だけを許す環 $\mathbb Z[\tfrac12]=\{m/2^k\mid m\in\mathbb Z,\ k\ge0\}$ でも $2$ は単元なので $2\mid3$ だが、$3\nmid 2$ である（$2=3\cdot m/2^k$ なら $2^{k+1}=3m$ となり、左辺は $3$ で割り切れない）。
一方、Gauss整数 の環 $\mathbb Z[i]$ では、整数どうしの整除は $\mathbb Z$ での整除と変わらない（prop-dvr-subring）。$\mathbb Z[i]$ で新しく起こるのは、整数でない元が整数を割り切ることで、$2=(1+i)(1-i)$ なので $1+i\mid 2$ である。
可換環 $R$ 上の多項式環 $R[x]$ で、$f(x)\in R[x]$ と $a\in R$ について
$$
x-a\ \mid\ f(x)-f(a)
$$
である。実際 $x^k-a^k=(x-a)(x^{k-1}+x^{k-2}a+\cdots+a^{k-1})$ なので、$f(x)-f(a)$ は各次数の項 $c_k(x^k-a^k)$ の和として $x-a$ の倍元である。$x$ に整数 $m$ を代入すれば、整数係数の多項式 $f$ と整数 $m,a$ について $m-a\mid f(m)-f(a)$ が得られる。たとえば $m-a\mid m^n-a^n$ であり、$7\mid 8^n-1$、$m-1\mid m^n-1$ である。
$\mathbb Z/6\mathbb Z$ では、$4=2\cdot2$ なので $2\mid4$、$2=4\cdot2$（$8\equiv2$）なので $4\mid2$ である。単元は $1,5$ で、$4=2\cdot5$ なので $2$ と $4$ は同伴である。一方 $2$ と $3$ は互いにどちらも割り切らない（$2\cdot c$ はいつも $0,2,4$ のどれかの類、$3\cdot c$ は $0$ か $3$ の類）。整数としては $2\mid4$ だが $4\nmid2$ であり、法 $6$ で見ると $2$ と $4$ が整除関係の上で区別できなくなる。
約数の順序を表で見る
$12=2^2\cdot3$ の正の約数を、$2$ の指数を行、$3$ の指数を列にとって並べると次の表になる。
| $3^0$ | $3^1$ | |
|---|---|---|
| $2^0$ | $1$ | $3$ |
| $2^1$ | $2$ | $6$ |
| $2^2$ | $4$ | $12$ |
表の中で $d$ が $d'$ を割り切るのは、$d'$ が $d$ から右と下へ（行と列の両方で番号が減らない向きへ）進んだ位置にあるときである。隣へ 1 つ進むことは素数を 1 つ掛けることにあたる。$1$ から $12$ まで 1 つずつ進む道は、下・下・右、下・右・下、右・下・下の $3$ 本で、それぞれ $1\mid2\mid4\mid12$、$1\mid2\mid6\mid12$、$1\mid3\mid6\mid12$ である。表の形が「長さ $3$ の数直線と長さ $2$ の数直線の積」であることが、主定理（thm-dvr-exponents）の内容であり、道の本数は cor-dvr-chains で数える。
反例の表
次の表は、整除関係について成り立ちそうで成り立たない推論を、条件を外した反例で示したものである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 正の整数に制限する | $\mathbb Z$ の $2$ と $-2$ | 反対称律（$2\mid-2$、$-2\mid2$ だが $2\neq-2$） |
| 同じ素数の冪どうし | $2$ と $3$ | どの 2 数も比べられること（$2\nmid3$、$3\nmid2$） |
| $b\neq0$ | $a=5$、$b=0$ | 「$a\mid b$ なら $a\le b$」（$5\mid0$ だが $5>0$） |
| 商が同じ環にある | $\mathbb Z\subset\mathbb Q$ の $2,3$ | 部分環での整除と大きい環での整除の一致（$\mathbb Q$ では $2\mid3$） |
| $a$ が素数 | $a=6$、$6\mid 4\cdot9$ | 「$a\mid bc$ なら $a\mid b$ または $a\mid c$」（$6\nmid4$、$6\nmid9$） |
| $a,b$ が互いに素 | $a=2$、$b=4$、$c=4$ | 「$a\mid c$、$b\mid c$ なら $ab\mid c$」（$8\nmid4$） |
| 有限個の元 | $S=\{1,2,3,4,\dots\}$ | $0$ でない公倍数の存在（最小公倍数が $0$ になる） |
最後の行は thm-dvr-complete-lattice の中で説明する。素数についての 5 行目は Euclid の補題（素数 の記事の補題「Euclidの補題」）が素数に固有の性質であることを、6 行目は互いに素の仮定の役割を示している。
性質
前順序としての整除関係
$R$ を可換環とし、$a,b,c,x,y\in R$ とする。
- $a\mid a$ である。$a\mid b$ かつ $b\mid c$ なら $a\mid c$ である。すなわち整除関係は $R$ 上の前順序である。
- $a\mid b$ かつ $a\mid c$ なら $a\mid bx+cy$ である。
- $a\mid b$ なら $ac\mid bc$ である。
- $a\mid b$ であることと、単項イデアルについて $(b)\subset(a)$ であることは同値である。
- $a=a\cdot1$ である。$b=ar$、$c=bs$ なら $c=a(rs)$ である。
- $b=ar$、$c=as$ なら $bx+cy=a(rx+sy)$ である。
- $b=ar$ なら $bc=(ac)r$ である。
- $(b)\subset(a)$ なら $b\in(a)$ なので $b=ar$ と書ける。逆に $b=ar$ なら $(b)$ の元 $bz$ は $a(rz)\in(a)$ である（単項イデアル の記事の命題「単項イデアルの包含と整除」の 1 と同じ）。$\square$
前順序から半順序を作る標準の方法は、互いに $\lesssim$ となる元を同一視することである（前順序 の記事の命題「同値類の半順序と普遍性」）。整除関係では「互いに割り切る」ことが同一視の関係で、整域ではこれは同伴であることと同じである。$\mathbb Z$ では $a$ と $-a$ を同一視することになり、各同値類からただ 1 つの $0$ 以上の代表元がとれる。こうして次の半順序集合が得られる。
- $(\mathbb Z_{\ge0},\mid)$ は半順序集合である。反対称律は、$a,b\ge0$ が互いに割り切るなら $b=\pm a$ で、ともに $0$ 以上だから $a=b$ となることによる。
- この順序で $1$ は最小元（$1\mid b$）、$0$ は最大元（$a\mid0$）である。数の大小では最小の $0$ が、整除の順序では最大になる。
- $b>0$ で $a\mid b$ なら $1\le a\le b$ である（約数 の記事の命題「割り切る関係の基本性質」の 6）。したがって正の整数の上では、「整除の順序で $a$ が $b$ 以下」なら「大小の順序で $a$ が $b$ 以下」であり、大小の順序は整除の順序を延長した全順序である。
部分環と整除
環を大きくすると割り切れる組は増える。$R\subset S$ が部分環で $a,b\in R$ のとき、$R$ の中で $b=ac$ となる $c$ があれば、それは $S$ の中でも同じ等式を満たすので、$R$ で $a\mid b$ なら $S$ でも $a\mid b$ である。ex-dvr-ring-dependence の $\mathbb Z\subset\mathbb Q$ のように逆は成り立たないが、大きい環が「新しい分数を含まない」なら逆も成り立つ。
$S$ を複素数体 $\mathbb C$ の部分環で、$S\cap\mathbb Q=\mathbb Z$ を満たすものとする。このとき整数 $a,b$ について、$S$ の中で $a\mid b$ であることと、$\mathbb Z$ の中で $a\mid b$ であることは同値である。とくに $S=\mathbb Z[i]$（Gauss整数 の環）はこの条件を満たす。
$\mathbb Z$ で $a\mid b$ なら、$\mathbb Z\subset S$ なので $S$ でも $a\mid b$ である。逆に $S$ の中で $b=ac$（$c\in S$）とする。$a=0$ なら $b=0$ であり、$\mathbb Z$ でも $0\mid0$ である。$a\neq0$ なら $c=b/a$ は有理数であり、$c\in S\cap\mathbb Q=\mathbb Z$ なので、$\mathbb Z$ の中で $a\mid b$ である。
$\mathbb Z[i]=\{x+yi\mid x,y\in\mathbb Z\}$ の元 $x+yi$ が有理数なら、虚部 $y$ は $0$ でなければならないので、$x+yi=x\in\mathbb Z$ である。よって $\mathbb Z[i]\cap\mathbb Q=\mathbb Z$ である。$\square$
同じ理由で、$\mathbb Z[\sqrt{-5}]=\{x+y\sqrt{-5}\mid x,y\in\mathbb Z\}$ なども条件を満たす。条件 $S\cap\mathbb Q=\mathbb Z$ を外すと結論は崩れ、$S=\mathbb Q$ や $S=\mathbb Z[\tfrac12]$ では $2\mid3$ となる（ex-dvr-ring-dependence）。整数の性質を調べるために $\mathbb Z[i]$ のような大きい環に移っても、整数どうしの整除の情報が失われも増えもしないことが、この命題の意味である。
主定理 1：$0$ 以上の整数は完備束をなす
$\mathbb Z$ のイデアルとは、空でない部分集合 $I$ で、$a,b\in I$、$z\in\mathbb Z$ なら $a+b\in I$、$az\in I$ となるものである（Sho08 §1.2、p. 5）。イデアルの族 $\{I_j\}_{j\in J}$ に対して、共通部分 $\bigcap_jI_j$ はイデアルであり（$J=\emptyset$ のときは $\mathbb Z$ と約束する）、有限個の $I_j$ の元の和全体 $\sum_jI_j$ は、すべての $I_j$ を含む最小のイデアルである（$J=\emptyset$ のときは $\{0\}$）。
$(\mathbb Z_{\ge0},\mid)$ は束であり、さらに完備束である。すなわち、任意の部分集合 $S\subset\mathbb Z_{\ge0}$（無限集合や空集合でもよい）は、整除の順序について下限と上限をもつ。具体的には次のとおりである。
- $S$ の下限は、イデアル $\sum_{s\in S}s\mathbb Z$ を $d\mathbb Z$ と書いたときの $d\ge0$ である。これを $\gcd S$ と書く。
- $S$ の上限は、イデアル $\bigcap_{s\in S}s\mathbb Z$ を $m\mathbb Z$ と書いたときの $m\ge0$ である。これを $\operatorname{lcm}S$ と書く。
2 元集合 $S=\{a,b\}$ では、下限と上限はそれぞれ最大公約数 $\gcd(a,b)$ と最小公倍数 $\operatorname{lcm}(a,b)$ である。
段 1（イデアルは単項で、生成元は $0$ 以上にただ 1 つ）． $\mathbb Z$ のイデアル $I$ に対し、$I=d\mathbb Z$ となる $d\ge0$ がただ 1 つある。$I=\{0\}$ なら $d=0$ である。そうでなければ $I$ は正の元を含む（$a\in I$ なら $-a=a\cdot(-1)\in I$）ので、その最小のもの $d$ をとる。$a\in I$ を $a=dq+r$（$0\le r< d$）と割ると（除法の原理）、$r=a-dq\in I$ であり、$d$ の最小性から $r=0$、すなわち $a\in d\mathbb Z$ である。逆に $d\mathbb Z\subset I$ は明らかである。$d\mathbb Z=e\mathbb Z$（$d,e\ge0$）なら $d,e$ は互いに割り切るので $d=e$ である（Sho08 Theorem 1.6、p. 6）。
段 2（順序を逆にする全単射）． 段 1 により、$a\mapsto a\mathbb Z$ は $\mathbb Z_{\ge0}$ から $\mathbb Z$ のイデアル全体への全単射であり、prop-dvr-preorder の 4 により
$$
a\mid b\iff b\mathbb Z\subset a\mathbb Z
$$
である。つまりこの全単射は、整除の順序をイデアルの包含の逆向きに移す。
段 3（下限）． $J:=\sum_{s\in S}s\mathbb Z=d\mathbb Z$ とする。各 $s\in S$ について $s\mathbb Z\subset J=d\mathbb Z$ なので $d\mid s$、すなわち $d$ は $S$ の下界である。$c\ge0$ が $S$ の下界なら、各 $s$ について $s\mathbb Z\subset c\mathbb Z$ であり、$c\mathbb Z$ はすべての $s\mathbb Z$ を含むイデアルなので、それらを含む最小のイデアル $J$ を含む。よって $d\mathbb Z\subset c\mathbb Z$、すなわち $c\mid d$ である。したがって $d$ は下界の中で最大、すなわち下限である。
段 4（上限）． $\bigcap_{s\in S}s\mathbb Z=m\mathbb Z$ とする。各 $s$ について $m\mathbb Z\subset s\mathbb Z$ なので $s\mid m$、すなわち $m$ は上界である。$c\ge0$ が上界なら、各 $s$ について $c\in s\mathbb Z$ なので $c\in m\mathbb Z$、すなわち $m\mid c$ である。したがって $m$ は上限である。
任意の部分集合が下限と上限をもつので、特に 2 元集合がもち、$(\mathbb Z_{\ge0},\mid)$ は束であり完備束である。2 元集合の場合、段 3 と段 4 の $d$、$m$ は「$a,b$ の公約数のうち、すべての公約数に割り切られるもの」「公倍数のうち、すべての公倍数を割り切るもの」であり、最大公約数 の記事の定理「公約数と最大公約数の約数」と 最小公倍数 の記事の定理「公倍数と最小公倍数の倍数」により、それぞれ $\gcd(a,b)$ と $\operatorname{lcm}(a,b)$ である。$\square$
自然数が最小公倍数と最大公約数について束になること、整除関係が半順序であることは BS12 Chapter I §1 の例（p. 4）にもある。定理の端の場合を見ておく。
- $S=\emptyset$ では、和は $\{0\}$、共通部分は $\mathbb Z$ なので、下限は $0$（最大元）、上限は $1$（最小元）である。空集合の下限が最大元になるのは、どんな数も空集合の下界だからである。
- $0\in S$ なら、$0\mathbb Z=\{0\}$ なので共通部分は $\{0\}$ で、上限は $0$ である。
- $S$ が無限個の正の整数からなるなら、上限は $0$ である。実際 $m>0$ の約数は $m$ 以下の有限個しかないので、$m$ が $S$ のすべての元に割り切られることはない。これが反例の表の最後の行で、「最小公倍数」は整除の順序の上限として $0$ になるが、大小の意味で最小の正の公倍数は存在しない。
空でない部分集合 $S\subset\mathbb Z_{\ge0}$ の最大公約数 $\gcd S$ は、$S$ の有限個の元の整数係数の 1 次結合として書ける。とくに、$S$ の有限部分集合 $S_0$ で $\gcd S_0=\gcd S$ となるものがある。
$d=\gcd S$ は $\sum_{s\in S}s\mathbb Z$ の元なので、定義により有限個の $s_1,\dots,s_k\in S$ と整数 $z_1,\dots,z_k$ で $d=s_1z_1+\cdots+s_kz_k$ と書ける。$S_0=\{s_1,\dots,s_k\}$ とすると、$d$ は $S_0$ の各元を割り切るので $S_0$ の公約数であり、$S_0$ の公約数 $c$ は 1 次結合 $d$ を割り切る。よって $\gcd S_0=d$ である。$\square$
$S=\{n^3-n\mid n\ge2\}=\{6,24,60,120,210,\dots\}$ の最大公約数は $6$ である。$n^3-n=(n-1)n(n+1)$ は連続する 3 整数の積なので $2$ と $3$ で割り切れ、$6$ は下界である。$6\in S$ なので、下界 $c$ は $6$ を割り切る。無限集合の最大公約数が、有限部分集合 $\{6\}$ ですでに決まっている例である。
主定理 2：素因数の指数による表示
素数全体の集合を $\mathcal P$ と書く。関数 $e\colon\mathcal P\to\mathbb Z_{\ge0}$ で、有限個の素数を除いて $e(p)=0$ となるもの全体を $\mathbb N^{(\mathcal P)}$ と書き、成分ごとの大小
$$
e\le e'\ :\iff\ \text{すべての素数 }p\text{ について }e(p)\le e'(p)
$$
で順序を入れる。正の整数 $n$ と素数 $p$ について、$n$ を割り切る $p$ の冪の最大の指数を $v_p(n)$ と書く（p進付値）。
写像
$$
v\colon\mathbb Z_{>0}\to\mathbb N^{(\mathcal P)},\qquad n\mapsto\bigl(v_p(n)\bigr)_{p\in\mathcal P}
$$
は全単射であり、正の整数 $a,b$ について
$$
a\mid b\iff v(a)\le v(b)
$$
が成り立つ。すなわち $v$ は半順序集合の同型 $(\mathbb Z_{>0},\mid)\cong(\mathbb N^{(\mathcal P)},\le)$ である。この同型で、積は成分ごとの和に、最大公約数は成分ごとの最小に、最小公倍数は成分ごとの最大に対応する。とくに $(\mathbb Z_{>0},\mid)$ は分配束である。また $n=p_1^{e_1}\cdots p_k^{e_k}$（$p_i$ は相異なる素数）の正の約数全体 $D(n)$ は、整除の順序について、長さ $e_1,\dots,e_k$ の鎖の直積 $\{0,\dots,e_1\}\times\cdots\times\{0,\dots,e_k\}$ に同型である。
$n$ を割り切る素数は有限個なので、$v(n)$ は $\mathbb N^{(\mathcal P)}$ の元である。$e\in\mathbb N^{(\mathcal P)}$ に対し $n=\prod_pp^{e(p)}$（有限積）とおくと、素因数分解の一意性（素数 の記事の定理「算術の基本定理」）により $v(n)=e$ であり、$v(n)=v(n')$ なら $n,n'$ の素因数分解が一致するので $n=n'$ である。よって $v$ は全単射である。
$a\mid b$ なら $b=ac$ で、$v_p(b)=v_p(a)+v_p(c)\ge v_p(a)$ である（p進付値 の記事の命題「付値の基本性質」の 1）。逆に $v(a)\le v(b)$ なら $c=\prod_pp^{v_p(b)-v_p(a)}$ は正の整数で、$v(ac)=v(a)+v(c)=v(b)$ なので、$v$ の単射性から $ac=b$、すなわち $a\mid b$ である。積が和に対応することは付値の加法性そのものである。この同値は 最大公約数 の記事の定理「素因数分解による最大公約数と最小公倍数」の 1 と同じ内容である。
順序の同型は下限と上限を保つ。$\mathbb N^{(\mathcal P)}$ で 2 元 $e,e'$ の下限と上限は成分ごとの $\min$ と $\max$ である（各成分が全順序なので、成分ごとの $\min$ は下界で、どの下界も成分ごとにそれ以下である。$\max$ も同様）。したがって $v(\gcd(a,b))_p=\min(v_p(a),v_p(b))$、$v(\operatorname{lcm}(a,b))_p=\max(v_p(a),v_p(b))$ である。これは 最大公約数 の記事の定理「素因数分解による最大公約数と最小公倍数」の 2 である。分配律は 最小公倍数 の記事の命題「最大公約数と最小公倍数の分配法則」であり、$(\mathbb Z_{>0},\mid)$ は分配束である。
最後に、$d\mid n$ は $v(d)\le v(n)$ と同値なので、$d$ の指数は $p_1,\dots,p_k$ 以外で $0$、$p_i$ で $0$ 以上 $e_i$ 以下である。$d\mapsto(v_{p_1}(d),\dots,v_{p_k}(d))$ が求める同型である。$\square$
$a\mid b$ と指数の比較の同値は Sho08 (1.4)（§1.3、p. 10）にもある。この定理が直感節の 3 つ目の見方の正確な形であり、「$2$ と $3$ が比べられない」のは、$v(2)$ と $v(3)$ が別々の成分に $1$ をもつ関数だからである。約数 の記事の定理「約数の個数と総和の公式」の $\tau(n)=\prod(e_i+1)$ は、鎖の直積 $D(n)$ の元の個数を数えたものにあたる。
$n$ が相異なる素数の積 $p_1\cdots p_k$（平方因子をもたない数）なら、$D(n)$ は $\{0,1\}^k$、すなわち $k$ 元集合 $\{p_1,\dots,p_k\}$ の部分集合全体の包含の順序と同型である。たとえば $D(30)$ の $8$ 個の約数は $\{2,3,5\}$ の $8$ 個の部分集合に対応し、$6=2\cdot3$ は $\{2,3\}$ に、$\gcd(6,10)=2$ は $\{2,3\}\cap\{2,5\}=\{2\}$ に対応する。
約数の鎖を数える
$d\mid d'$ かつ $d\neq d'$ で、$d\mid e\mid d'$ となる $e$ が $d$ と $d'$ だけのとき、$d'$ は $d$ を 被覆する という（半順序集合 の被覆関係）。$D(n)$ の中で $1$ から $n$ まで被覆関係だけでつないだ列
$$
1=d_0\mid d_1\mid\cdots\mid d_\ell=n\qquad(d_j\text{ は }d_{j-1}\text{ を被覆する})
$$
を、$1$ から $n$ への 極大鎖 という。$n$ の素因数を重複をこめて数えた個数を $\Omega(n)=e_1+\cdots+e_k$ と書く。
$n=p_1^{e_1}\cdots p_k^{e_k}$ を正の整数とする。
- $d\mid d'$ となる正の整数について、$d'$ が $d$ を被覆するのは $d'/d$ が素数のとき、かつそのときに限る。
- $1$ から $n$ への極大鎖の長さ（上の $\ell$ に当たる段数）はどれも $\Omega(n)$ である。
- $1$ から $n$ への極大鎖の本数は、多項係数
$$ \frac{\Omega(n)!}{e_1!\,e_2!\cdots e_k!} $$
である。 - $d\mapsto n/d$ は $D(n)$ から $D(n)$ への全単射で、整除の順序を逆にする（$d\mid d'\iff n/d'\mid n/d$）。
- $d'/d=q$ が素数で $d\mid e\mid d'$ なら、$e/d$ は $q$ の正の約数なので $1$ か $q$、すなわち $e=d$ か $e=d'$ である。逆に $r=d'/d$ が $1$ より大きく素数でないなら、$r$ の素因数 $q$ をとると $q< r$ で、$e=dq$ は $d\mid e\mid d'$、$d\neq e\neq d'$ を満たすので、$d'$ は $d$ を被覆しない。
2・3. 極大鎖 $1=d_0\mid\cdots\mid d_\ell=n$ に、比の列 $(q_1,\dots,q_\ell)$、$q_j=d_j/d_{j-1}$ を対応させる。1 により各 $q_j$ は素数で、$q_1q_2\cdots q_\ell=n$ である。素因数分解の一意性により、この列は $p_1$ を $e_1$ 個、…、$p_k$ を $e_k$ 個並べたものである。とくに $\ell=\Omega(n)$ である。逆に、そのような並べ方 $(q_1,\dots,q_\ell)$ から $d_j=q_1\cdots q_j$ とおけば、1 により極大鎖が得られ、2 つの対応は互いに逆である。よって極大鎖の本数は、$\Omega(n)$ 個の場所に $p_i$ を $e_i$ 個ずつ並べる並べ方の数、すなわち多項係数に等しい。 - $n/(n/d)=d$ なので、$d\mapsto n/d$ は自分自身が逆写像である全単射である。$d\mid d'$ なら $n/d=(n/d')\cdot(d'/d)$ なので $n/d'\mid n/d$ であり、逆向きも同じ計算を $n/d',n/d$ に当てはめればよい。$\square$
$360=2^3\cdot3^2\cdot5$ では $\Omega(360)=6$ で、$1$ から $360$ への極大鎖は $\dfrac{6!}{3!\,2!\,1!}=60$ 本あり、どれも $6$ 段である。たとえば $1\mid2\mid4\mid8\mid24\mid72\mid360$ は並べ方 $(2,2,2,3,3,5)$ に、$1\mid5\mid15\mid45\mid90\mid180\mid360$ は $(5,3,3,2,2,2)$ に対応する。$12=2^2\cdot3$ では $\dfrac{3!}{2!\,1!}=3$ 本で、表の節で数えた $3$ 本の道と一致する。
4 の対応 $d\mapsto n/d$ は、約数 の記事の命題「約数の組 $d$ と $\frac{n}{d}$」で約数を組にしたときの相手をとる操作であり、表の上では表を上下左右とも反転させる操作にあたる。
整除についての帰納法
$(\mathbb Z_{>0},\mid)$ について次が成り立つ。
- 空でない部分集合は、整除の順序について極小元（それを割り切る元が自分以外にない元）をもつ。
- $b_0,b_1,b_2,\dots$ で $b_{j+1}\mid b_j$、$b_{j+1}\neq b_j$ がすべての $j$ で成り立つ無限列は存在しない。
- 各 $n$ について、$n$ を割り切る元は有限個である。
- 素数全体は、どの 2 つも比べられない無限集合（無限の反鎖）である。
- 空でない部分集合 $A$ の中で大小の意味で最小の元 $a$ をとる。$b\in A$ が $b\mid a$ なら $b\le a$ なので $b=a$ であり、$a$ は整除の順序について極小である。
- そのような列があれば、$b_{j+1}\mid b_j$ から $b_{j+1}\le b_j$ で、$b_{j+1}\neq b_j$ なので $b_0>b_1>b_2>\cdots$ は正の整数の無限の減少列となり、ありえない。
- $n$ の約数は $1$ 以上 $n$ 以下である。
- 素数は無限に多い（素数 の記事の定理「素数の無限性」）。素数 $p,q$ で $p\mid q$ なら、$p$ は $q$ の $1$ でない正の約数なので $p=q$ である。$\square$
1 により、正の整数についての主張を「$n$ の $n$ 以外の約数すべてで成り立つなら $n$ でも成り立つ」という形の帰納法で示すことができる。たとえば Möbius関数 $\mu$ は、$\mu(1)=1$ と「$n>1$ なら $\sum_{d\mid n}\mu(d)=0$」によって、$n$ の真の約数での値から $\mu(n)$ を決める形で定義できる。一方 4 により、整除の順序は大小の順序と違って、どの 2 数も比べられるという性質から遠い。3 と 4 は、整除の順序が「下には有限、横には無限に広い」ことを表している。
補足
一意分解整域では、同伴な素元を同一視すれば、各素元の指数を比べることで thm-dvr-exponents と同じ形の記述が得られる。素元分解が一意でない環では、元の整除よりもイデアルの包含の方が扱いやすい。Dedekind整域では、$0$ でないイデアル $I,J$ について「$I\subset J$ ならば $I=JL$ となるイデアル $L$ がある」ことが成り立ち（Dedekind整域 の記事の定理「Dedekind整域のイデアル論的特徴づけ」の 4）、イデアルの包含がイデアルの整除にちょうど一致する。prop-dvr-preorder の 4 の「割り切ることは含まれること」が、イデアルの世界で逆向きにも成り立つわけである。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
