Euclidの補題
概要
Euclidの補題（Euclid's lemma）とは、素数 $p$ が整数の積 $ab$ を割り切るならば $p$ は $a$ と $b$ の少なくとも一方を割り切るという定理であり、逆に $2$ 以上の整数でこの性質をもつものは素数に限る。証明は割り算の定理と整列性、または Bézout の等式による。素因数分解の一意性の要であり、素数 $p$ を法とする剰余環 $\mathbb{Z}/p\mathbb{Z}$ が体であることや、$0< k< p$ のとき $p$ が二項係数 $\binom pk$ を割り切ることもこの補題から従う。整域では「既約元は素元」という形になり、単項イデアル整域では成り立つが、$\mathbb{Z}[\sqrt{-5}]$ では既約元 $2$ が $(1+\sqrt{-5})(1-\sqrt{-5})$ を割り切ってもどちらの因子も割り切らない。
前提知識: 素数, 最大公約数, 整数の割り算と互除法
Euclidの補題（Euclid's lemma）とは、素数 $p$ が 2 つの整数の積 $ab$ を割り切るならば、$p$ は $a$ と $b$ の少なくとも一方を割り切る、という整数の性質である。逆に、$2$ 以上の整数でこの性質をもつものは素数に限るので、この性質は素数の別の特徴づけにもなっている。
素数の定義は「$1$ と自分自身以外に正の約数をもたない」、つまり「これ以上小さな因子に分けられない」という性質である。ところが、素因数分解の一意性をはじめとする整数論の多くの議論で実際に使うのは、「積を割り切るなら因子のどちらかを割り切る」という性質のほうである。Euclid の補題は、整数ではこの 2 つの性質が一致することを述べる。この一致は当たり前ではなく、割り算の定理（余りが割る数より小さくなるように割れること）に支えられている。整数以外の数の体系、たとえば $\mathbb{Z}[\sqrt{-5}]$ では一致が崩れ、それに伴って素因数分解の一意性も崩れる。
この記事では、Euclid の補題とその逆を証明し、積が多い場合、$p$ を法とする合同式、二項係数への帰結を導く。最後に、整数以外の環での形と、条件を外すと成り立たなくなる例を挙げる。
| 結果 | 内容 | 仮定 |
|---|---|---|
| thm-euclem-main | $p\mid ab$ なら $p\mid a$ または $p\mid b$ | $p$ は素数 |
| thm-euclem-converse | 上の性質をもつ $2$ 以上の整数は素数 | $p\ge2$ |
| cor-euclem-product | $p\mid a_1\cdots a_k$ なら、ある $a_j$ を $p$ が割り切る | $p$ は素数 |
| cor-euclem-mod | $\mathbb{Z}/p\mathbb{Z}$ は体 | $p$ は素数 |
| prop-euclem-binom | $p\mid\binom pk$ | $p$ は素数、$0< k< p$ |
定義と主張
以下、文字は特に断らない限り整数を表す。整数 $b$ と $a$ について、$a=bk$ となる整数 $k$ があるとき、$b$ は $a$ を割り切るといい、$b\mid a$ と書く。割り切らないときは $b\nmid a$ と書く。どの $b$ についても $b\mid0$ である（$0=b\cdot0$）。$2$ 以上の整数 $p$ の正の約数が $1$ と $p$ だけのとき、$p$ を素数という。
$p$ を素数、$a,b$ を整数とする。$p\mid ab$ ならば、$p\mid a$ または $p\mid b$ である。
証明は節「証明」にある。$a,b$ は負の数や $0$ でもよい。$a=0$ なら $p\mid a$ なので主張は自明に成り立つ。「または」は両方の場合を含む（$p=3$、$a=b=6$ では $3$ は $a$ と $b$ の両方を割り切る）。
$2$ 以上の整数 $p$ について、次は同値である。
- $p$ は素数である。
- 任意の整数 $a,b$ について、$p\mid ab$ ならば $p\mid a$ または $p\mid b$ である。
1 ⇒ 2 は thm-euclem-main であり、その証明は節「証明」にある。2 ⇒ 1 を対偶で示す。$p\ge2$ が素数でなければ、$p$ は $1$ と $p$ 以外の正の約数 $d$ をもち、$p=de$、$1< d< p$、$1< e< p$ と書ける。$p\mid de$ である。一方、$0< d< p$ なので $d$ は $p$ の倍数でなく、$p\nmid d$ である。同様に $p\nmid e$ である。よって $p$ は 2 の性質をもたない。$\square$
2 の性質を以下では Euclid の性質と呼ぶ。
$7\mid 21\cdot 10=210$ であり、$7\mid21$ である。$5\mid 12\cdot 15$ で、$5\nmid12$ なので $5\mid15$ でなければならず、実際そうである。素数でない $6$ では、$6\mid 4\cdot 9=36$ だが $6\nmid4$、$6\nmid9$ である。$6=2\cdot3$ の因子 $2$ が $4$ に、$3$ が $9$ に分かれて入っているためである。
証明
証明では、整数の次の 2 つの性質を使う（整数の割り算と互除法 の公理「整列性」と定理「割り算の定理」）。
- 整列性：$0$ 以上の整数からなる空でない集合には最小の元がある。
- 割り算の定理：整数 $x$ と正の整数 $d$ について、$x=dq+r$、$0\le r< d$ を満たす整数 $q,r$ がある。
$p\mid ab$ とし、$p\nmid a$ と仮定して $p\mid b$ を示す。集合
$$
I:=\{x\in\mathbb{Z}\mid p\mid xb\}
$$
を考える。$x,y\in I$ なら $p\mid xb+yb=(x+y)b$ なので $x+y\in I$ であり、$x\in I$ と整数 $k$ について $p\mid kxb$ なので $kx\in I$ である。$p\in I$（$p\mid pb$）であり、仮定から $a\in I$ である。
$p$ は $I$ に属する正の整数なので、整列性により $I$ に属する最小の正の整数 $d$ がある。$I$ の任意の元 $x$ を割り算の定理で $x=dq+r$（$0\le r< d$）と書くと、$r=x+(-q)d\in I$ である。$r>0$ なら $d$ の最小性に反するので $r=0$、すなわち $d\mid x$ である。したがって $d$ は $I$ のすべての元を割り切り、特に $d\mid p$ かつ $d\mid a$ である。
$d$ は $p$ の正の約数なので $d=1$ か $d=p$ である。$d=p$ なら $p\mid a$ となって仮定に反する。よって $d=1$ であり、$1\in I$、すなわち $p\mid b$ である。$\square$
証明に出てきた $I$ は、足し算と整数倍で閉じた $\mathbb{Z}$ の部分集合（$\mathbb{Z}$ のイデアル）であり、後半は「そのような集合は最小の正の元の倍数全体である」ことを示している。素数 $p$ の性質を使ったのは、最後の段の「$p$ の正の約数は $1$ と $p$ だけ」という 1 か所だけである。
同じ議論から、$\gcd(p,a)$ が $p$ と $a$ の整数係数の 1 次結合で書けること（Bézoutの等式）が出る。これを使うと証明はさらに短くなる。
$p\mid ab$、$p\nmid a$ とする。$\gcd(p,a)$ は $p$ の正の約数なので $1$ か $p$ であり、$p\nmid a$ より $p$ ではない。よって $\gcd(p,a)=1$ であり、Bézoutの等式 により $px+ay=1$ となる整数 $x,y$ がある。両辺に $b$ を掛けると
$$
b=p(bx)+(ab)y
$$
であり、右辺の 2 つの項はどちらも $p$ で割り切れる。よって $p\mid b$ である。$\square$
最大公約数を使わず、最小の反例を考える証明もある。
要点：$p\nmid a$ を固定し、$p\mid ab$ かつ $p\nmid b$ となる最小の正の $b$ をとると、$p$ を $b$ で割った余りがもっと小さな同じ性質の数になって矛盾する。
詳しい証明を開く
$p\mid ab$、$p\nmid a$、$p\nmid b$ となる $a,b$ があったとする。$b$ を $p$ で割った余りを $b'$ とすると、$b=pq+b'$、$0\le b'< p$ で、$p\nmid b$ から $b'\ne0$、また $ab'=ab-apq$ は $p$ で割り切れる。そこで、この $a$ を固定し、「$p\mid ab$ かつ $p\nmid b$」を満たす正の整数 $b$ のうち最小のものをとる（整列性）。上の議論により $1\le b\le p-1$ である。
$b=1$ なら $p\mid a$ となって $p\nmid a$ に反するので、$2\le b\le p-1$ である。$p$ を $b$ で割って $p=bs+r$、$0\le r< b$ とする。$r=0$ なら $b$ は $p$ の約数で $1< b< p$ となり、$p$ が素数であることに反する。よって $0< r< b$ である。すると $ar=ap-abs$ は $p$ で割り切れ、$0< r< p$ なので $p\nmid r$ である。これは $b$ の最小性に反する。$\square$
帰結
$p$ を素数とする。
- $p\mid a_1a_2\cdots a_k$ ならば、ある $j$ について $p\mid a_j$ である。
- 特に、$p\mid a^n$（$n\ge1$）ならば $p\mid a$ である。
- $a_1,\dots,a_k$ がすべて素数で $p\mid a_1\cdots a_k$ ならば、$p$ はどれかの $a_j$ に等しい。
1：$k$ についての帰納法で示す。$k=1$ は明らかである。$k\ge2$ のとき $a_1\cdots a_k=(a_1\cdots a_{k-1})\,a_k$ に thm-euclem-main を使うと、$p\mid a_k$ か $p\mid a_1\cdots a_{k-1}$ であり、後者なら帰納法の仮定により $p\mid a_j$（$j< k$）である。
2：1 で $a_1=\cdots=a_n=a$ とすればよい。
3：1 により $p\mid a_j$ となる $j$ がある。$a_j$ は素数なので正の約数は $1$ と $a_j$ だけであり、$p\ge2$ なので $p=a_j$ である。$\square$
3 は、素因数分解の一意性の証明の中心である。$p_1\cdots p_r=q_1\cdots q_s$（どれも素数）なら、3 により $p_r$ はどれかの $q_j$ に等しいので、両辺から 1 つずつ消すことができ、$r$ についての帰納法で 2 つの分解が並べ替えを除いて一致する（素因数分解の一意性 の定理「算術の基本定理」）。
合同式の言葉では、Euclid の補題は「$p$ を法として $0$ でない数どうしの積は $0$ にならない」ことである。
$p$ を素数とする。
- $ab\equiv0\pmod p$ ならば、$a\equiv0$ または $b\equiv0\pmod p$ である。
- $c\not\equiv0\pmod p$ のとき、$ac\equiv bc\pmod p$ ならば $a\equiv b\pmod p$ である。
- $\mathbb{Z}/p\mathbb{Z}$ は体である。すなわち、$c\not\equiv0\pmod p$ なら $cc'\equiv1\pmod p$ となる整数 $c'$ がある。
1 は thm-euclem-main を合同式で書き直したものである。2：$(a-b)c\equiv0$ に 1 を使うと、$c\not\equiv0$ なので $a-b\equiv0$ である。3：$p$ で割った余り $0,1,\dots,p-1$ の集合を $R$ とし、$x\in R$ に $xc$ を $p$ で割った余りを対応させる写像 $R\to R$ を考える。2 によりこの写像は単射であり、$R$ は有限集合なので全射でもある。よって $xc\equiv1$ となる $x$ がある。$\square$
合成数 $n$ を法とすると 1 は成り立たない。$2\cdot3\equiv0\pmod6$ だが、$2\not\equiv0$、$3\not\equiv0\pmod6$ である。
$p$ を素数、$0< k< p$ とすると、$p\mid\binom pk$ である。
$\binom pk$ は整数で、$k!\,(p-k)!\binom pk=p!$ である。右辺は $p$ で割り切れる。左辺の $k!\,(p-k)!$ は $1$ 以上 $p-1$ 以下の整数の積なので、$p$ がこれを割り切れば cor-euclem-product の 1 により $p$ はある $j$（$1\le j\le p-1$）を割り切ることになり、$0< j< p$ に反する。よって $p\nmid k!\,(p-k)!$ であり、$p\mid k!\,(p-k)!\cdot\binom pk$ に thm-euclem-main を使うと $p\mid\binom pk$ である。$\square$
この命題から $(a+b)^p\equiv a^p+b^p\pmod p$ が出て、Fermatの小定理の証明の 1 つになる。$p$ が素数でなければ成り立たない。$\binom42=6$ は $4$ で割り切れない。
素数 $p$ について $\sqrt p$ は無理数である。有理数だとすると $\sqrt p=m/n$（$m,n$ は正の整数）と書け、分子と分母をそれらの最大公約数で割って $\gcd(m,n)=1$ としてよい。$m^2=pn^2$ なので $p\mid m^2$ であり、cor-euclem-product の 2 により $p\mid m$ である。$m=pm'$ とおくと $p^2m'^2=pn^2$、すなわち $pm'^2=n^2$ なので、同様に $p\mid n$ である。$p$ は $m,n$ の公約数になり、$\gcd(m,n)=1$ に反する。
互いに素な数への一般化
Euclid の補題は、次の形に一般化される：$\gcd(a,b)=1$ かつ $a\mid bc$ ならば $a\mid c$ である（互いに素 の命題「互いに素な因子の消去」）。$a$ が素数 $p$ のときは、$p\nmid b$ と $\gcd(p,b)=1$ が同値なので、これは Euclid の補題そのものである。一般化された形では、互いに素という仮定を外せない。$a=4$、$b=2$、$c=6$ では $4\mid bc=12$ だが $4\nmid6$ である。
整数以外の環で
この節では、環は乗法について可換で単位元 $1$ をもち、$0$ でない 2 つの元の積が $0$ にならない（整域）とする。環 $R$ の元 $\varepsilon$ が $\varepsilon\eta=1$ となる $\eta\in R$ をもつとき $\varepsilon$ を単元といい、$\alpha,\beta\in R$ について $\alpha=\beta\gamma$ となる $\gamma\in R$ があるとき $\beta\mid\alpha$ と書く。$0$ でも単元でもない元 $\pi$ について、
- $\pi=\beta\gamma$ ならば $\beta$ か $\gamma$ が単元であるとき、$\pi$ を既約元という（「分けられない」性質。既約元）。
- $\pi\mid\beta\gamma$ ならば $\pi\mid\beta$ または $\pi\mid\gamma$ であるとき、$\pi$ を素元という（Euclid の性質。素元）。
$\mathbb{Z}$ の単元は $\pm1$ であり、既約元は $\pm p$（$p$ は素数）である。thm-euclem-converse は「$\mathbb{Z}$ では既約元と素元が一致する」と言い換えられる。一般の整域では、素元はつねに既約元である（素元 の命題「素元から既約元へ」、DF04 §8.3 Proposition 10）。Euclid の補題に当たるのは逆向きの「既約元は素元である」で、これは環によって成り立ったり成り立たなかったりする。 - 成り立つ環：単項イデアル整域（既約元 の系「単項イデアル整域の既約元」、DF04 §8.3 Proposition 11）。特に体 $K$ 上の多項式環 $K[X]$（多項式環 の命題「既約多項式に関する Euclid の補題」）と Gauss 整数の環 $\mathbb{Z}[i]$（素因数分解の一意性 の定理「Gauss 整数の Euclid の補題」）。一意分解整域でも成り立つ（素元 の定理「一意分解整域の素元判定」）。
- 成り立たない環：次の 2 つの例。
$R=\mathbb{Z}[\sqrt{-5}]=\{a+b\sqrt{-5}\mid a,b\in\mathbb{Z}\}$ では、$2$ は既約元だが素元でない。したがって $R$ では「既約元は素元」という形の Euclid の補題が成り立たない。
確かめる。$\alpha=a+b\sqrt{-5}$ に $N(\alpha):=a^2+5b^2=|\alpha|^2$ を対応させると、$N(\alpha\beta)=N(\alpha)N(\beta)$ である。$\varepsilon\eta=1$ なら $N(\varepsilon)N(\eta)=1$ なので単元のノルムは $1$ で、$a^2+5b^2=1$ から単元は $\pm1$ だけである。$2=\beta\gamma$ で $\beta,\gamma$ がともに単元でないとすると $N(\beta)N(\gamma)=4$、$N(\beta),N(\gamma)\ge2$ から $N(\beta)=2$ となるが、$a^2+5b^2=2$ を満たす整数はない（$b\ne0$ なら $5$ 以上、$b=0$ なら平方数）。よって $2$ は既約元である。一方
$$
(1+\sqrt{-5})(1-\sqrt{-5})=6=2\cdot3
$$
なので $2\mid(1+\sqrt{-5})(1-\sqrt{-5})$ だが、$1\pm\sqrt{-5}=2(c+d\sqrt{-5})$ とすると実部を比べて $2c=1$ となり、$c$ が整数であることに反する。よって $2\nmid1+\sqrt{-5}$、$2\nmid1-\sqrt{-5}$ であり、$2$ は素元でない。
$3$ と $1\pm\sqrt{-5}$ もノルムがそれぞれ $9$、$6$ で、ノルム $2$ や $3$ の元がないことから同じ議論で既約元である。$2$ と $1\pm\sqrt{-5}$ はノルムが違うので単元倍の関係になく、$6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ は順序と単元倍を除いても一致しない 2 通りの既約元への分解である。$R$ では素因数分解の一意性も成り立たない（素因数分解の一意性）。
体 $k$ 上の 1 変数多項式のうち $t$ の 1 次の係数が $0$ のものの全体 $R=k[t^2,t^3]=\{c_0+c_2t^2+c_3t^3+\cdots\}$ は整域である。$R$ で $t^2$ は既約元だが、$t^2\mid t^3\cdot t^3=t^6$（$t^6=t^2\cdot t^4$、$t^4\in R$）なのに $t^2\nmid t^3$ である。
確かめる。$R$ の単元は $k[t]$ の単元である $0$ でない定数に限る。$R$ には次数 $1$ の元がないので、$t^2=\beta\gamma$ なら次数の和 $\deg\beta+\deg\gamma=2$ から一方は次数 $0$、すなわち $0$ でない定数で単元である。よって $t^2$ は既約元である。$t^3=t^2\gamma$ となる多項式は $\gamma=t$ だけだが、$t\notin R$ なので $t^2\nmid t^3$ である。
どちらの環でも、Euclid の補題の証明（prf-euclem-main）の「最小の元で割ると余りが小さくなる」という一歩が使えない。$\mathbb{Z}[\sqrt{-5}]$ では $2$ と $1+\sqrt{-5}$ の 1 次結合の全体は 1 つの元の倍数全体にならない（素因数分解の一意性 の命題「割り算の定理とイデアルの単項性が崩れる」）。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $p$ が素数 | $p=6$、$a=4$、$b=9$ | $p\mid ab$ ならば $p\mid a$ または $p\mid b$ |
| $\gcd(a,b)=1$（一般化された形） | $a=4$、$b=2$、$c=6$ | $a\mid bc$ なら $a\mid c$ |
| 環が $\mathbb{Z}$（単項イデアル整域） | $\mathbb{Z}[\sqrt{-5}]$ の既約元 $2$ | 既約元が積を割り切れば因子のどちらかを割り切る |
| 環が $\mathbb{Z}$（単項イデアル整域） | $k[t^2,t^3]$ の既約元 $t^2$ | 既約元が積を割り切れば因子のどちらかを割り切る |
名前について
この補題は Euclid『原論』第 7 巻命題 30 にある（HW60 第 1 章の注、p. 10）。HW60 はこれを Theorem 3（Euclid's first theorem、p. 3）として述べ、§2.10（p. 21）で 1 次結合を使って証明し、§2.11（p. 21）では最小の反例を使って素因数分解の一意性を直接示している。Ste17 では Theorem 1.1.19（p. 7）である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
