素因数分解

同義語：prime factorization

概要

前提知識: 整数, 素数, 約数

$360$ を小さい数の積に分けていくと、たとえば $360=4\cdot90=(2\cdot2)\cdot(2\cdot45)=(2\cdot2)\cdot(2\cdot(3\cdot15))=2\cdot2\cdot2\cdot3\cdot3\cdot5$ となる。別の順に $360=8\cdot45=(2\cdot2\cdot2)\cdot(3\cdot3\cdot5)$ と分けても、$360=10\cdot36=(2\cdot5)\cdot(2\cdot2\cdot3\cdot3)$ と分けても、最後に現れる素数は同じ $2,2,2,3,3,5$ であり、まとめて $360=2^3\cdot3^2\cdot5$ と書ける。これが $360$ の 素因数分解 である。$360$ の正の約数は $2^a3^b5^c$（$0\le a\le3$、$0\le b\le2$、$0\le c\le1$）の形の数に限られるので、その個数は $(3+1)(2+1)(1+1)=24$ と、割り算を 1 つずつ試さずに求まる。
どんな分け方をしても同じ素数の組にたどり着くことは、素数の記事の定理「算術の基本定理」が保証する。本記事はこの定理を前提に、素因数分解そのもの、すなわち指数を取り出す関数 $v_p$ とその計算規則、有理数への拡張、平方数と冪の判定、実際に分解を求める手順（試し割り）、そして一意性が成り立たない数の世界を扱う。約数・最大公約数・最小公倍数・Eulerのφ関数など、初等整数論の多くの量は素因数分解の指数から読み取れる。

定義

$2$ 以上の整数 $n$ を有限個の素数の積
$$ n=p_1p_2\cdots p_r\qquad(r\ge1) $$
として表すことを $n$ の 素因数分解（prime factorization）といい、各 $p_i$ を $n$ の 素因数（prime factor）という。素数の記事の定理「算術の基本定理」により、素因数分解は存在し、因子の並べ方の違いを除いてただ 1 通りである。そこで同じ素数をまとめて小さい順に並べる。

素因数分解の標準形

$2$ 以上の整数 $n$ を
$$ n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\qquad(p_1< p_2<\cdots< p_k\ \text{は素数},\ e_i\ge1) $$
と書いたものを $n$ の素因数分解の 標準形 という。$n=1$ は $k=0$ の場合（空の積）とみなし、$1$ の標準形は素数を 1 つも含まない。$0$ でない負の整数 $n$ については $n=-|n|$ とし、$|n|$ の標準形に符号 $-1$ を付けたものを考える。

標準形の指数 $e_i$ は、素数ごとの関数として扱うと便利である。

素因数ごとの指数

素数 $p$ と $0$ でない整数 $n$ について、$|n|$ の標準形に $p$ が現れるならその指数を、現れないなら $0$ を $v_p(n)$ と書き、$n$ の $p$ 進付値（$p$-adic valuation）という（p進付値）。$v_p(0)=\infty$ と約束する。

この記号を使うと、$0$ でない整数 $n$ は、すべての素数 $p$ にわたる積として
$$ n=\pm\prod_pp^{v_p(n)} $$
と書ける。$v_p(n)\neq0$ となる $p$ は有限個なので、右辺は実質的に有限個の因子の積である。たとえば $v_2(360)=3$、$v_3(360)=2$、$v_5(360)=1$ で、$p\ge7$ では $v_p(360)=0$ である。$v_p(n)$ は「$p^e$ が $n$ を割り切る最大の $e$」とも言える（prop-pfac-valuation の 1）。文献によっては $v_p$ を $\operatorname{ord}_p$ や $\nu_p$ と書く（たとえば Sho08 §1.3、p. 10 は $\nu_p$ と書く）。

直感

素数は掛け算についての「原子」であり、素因数分解は整数を原子の組合せとして書いた化学式にあたる。算術の基本定理が言っているのは、化学式が物質ごとにただ 1 つに決まるということである。したがって整数 $n\ge1$ は、指数の列 $(v_2(n),v_3(n),v_5(n),v_7(n),\dots)$（有限個を除いて $0$）と 1 対 1 に対応し、掛け算は指数の足し算に、割り切る関係は指数の大小に、最大公約数と最小公倍数は指数の最小と最大に対応する。整数の乗法の問題を、指数についての足し算と大小の問題に翻訳できるのが素因数分解の効用である。
一方で、素因数分解を実際に求めるのは難しい。$n$ が与えられても、どの素数で割り切れるかは試してみないと分からず、素朴な方法では $\sqrt n$ 程度の回数の割り算が必要になる（prop-pfac-trial-division）。RSA暗号の安全性は、大きな数の素因数分解が現実的な時間ではできないと信じられていることに依拠している（rem-pfac-complexity）。

例と反例

小さな数の標準形

$12=2^2\cdot3$、$60=2^2\cdot3\cdot5$、$97=97$（素数は自分自身が標準形）、$1001=7\cdot11\cdot13$、$1024=2^{10}$、$10!=3628800=2^8\cdot3^4\cdot5^2\cdot7$ である。$10!$ の指数は、階乗の記事の定理「Legendre の公式」$v_p(n!)=\sum_{r\ge1}\lfloor n/p^r\rfloor$ により $v_2(10!)=5+2+1=8$、$v_3(10!)=3+1=4$、$v_5(10!)=2$、$v_7(10!)=1$ と、$10!$ を計算しなくても求まる（$\lfloor\cdot\rfloor$ は床関数）。

試し割りによる分解

$9991$ を分解する。$2,3,5,7,\dots$ と小さい数から順に割っていくと、$96$ までのどの数でも割り切れず、$97$ で初めて $9991=97\cdot103$ と割り切れる。残りの $103$ については $97^2=9409>103$ なので、$103$ は素数である（prop-pfac-trial-division）。よって $9991=97\cdot103$ が標準形である。この例では $9991=100^2-3^2=(100-3)(100+3)$ と気づけば割り算なしで分解できるが、そのような近道がいつもあるわけではない。

反例：偶数だけの世界では分解が一意でない

正の偶数全体 $E=\{2,4,6,8,\dots\}$ は掛け算で閉じているが、$1$ を含まない。$E$ の元 $n$ で、$E$ の 2 元の積 $n=ab$（$a,b\in E$）に書けないものを「$E$ の素数」と呼ぶことにする。
$E$ の素数はちょうど $4$ で割って $2$ 余る数 $2,6,10,14,18,\dots$ である。実際、$n=ab$（$a,b$ は偶数）なら $4\mid n$ である。逆に $4\mid n$ なら $n=2\cdot(n/2)$ で $n/2$ は偶数なので、$n$ は $E$ の 2 元の積である。
$E$ のどの元も $E$ の素数の積に書ける。$n=2^ab$（$a\ge1$、$b$ は奇数）なら、$n=2^{a-1}\cdot(2b)$ は $a-1$ 個の $2$ と $2b$ の積で、$2$ と $2b$ はどちらも $4$ で割って $2$ 余るからである。しかし
$$ 36=6\cdot6=2\cdot18 $$
であり、$2,6,18$ はどれも $E$ の素数なので、$36$ は $E$ の素数の積として 2 通りに書ける。$E$ の素数 $6$ は $2\cdot18$ を割り切る（商 $6$ が $E$ に属する）が、$2$ も $18$ も割り切らない（$18/6=3\notin E$）。
$E$ は掛け算で閉じていることを満たし、$1$ を含むことと「素数が積を割り切るなら因子のどれかを割り切る」こと（素数の記事の補題「Euclidの補題」の性質）を満たさない。破れるのは「掛け算で閉じた数の集まりでは、それ以上分解できない元への分解は一意である」という含意である。$4$ で割って $1$ 余る数の世界での同様の例 $441=9\cdot49=21\cdot21$ は、素数の記事の例「反例：一意分解が崩れる数の世界」にある。

反例：整数を拡げた環での 2 通りの分解

$\mathbb{Z}[\sqrt{-5}]=\{x+y\sqrt{-5}\mid x,y\in\mathbb{Z}\}$ は $1$ を含み、足し算・引き算・掛け算で閉じた整域である。ここで
$$ 6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5}) $$
となる。この 2 つの分解が本質的に異なることを、ノルム $N(x+y\sqrt{-5}):=x^2+5y^2$（複素数としての絶対値の 2 乗）で確かめる。$N(\alpha\beta)=N(\alpha)N(\beta)$ が成り立つ。

単元（逆元をもつ元）は $\pm1$ だけである。$\alpha\beta=1$ なら $N(\alpha)N(\beta)=1$ で、$x^2+5y^2=1$ の解は $(x,y)=(\pm1,0)$ だけだからである。
$2,3,1+\sqrt{-5},1-\sqrt{-5}$ のノルムは $4,9,6,6$ である。これらのどれかが単元でない 2 元の積 $\beta\gamma$ に書けたとすると、$N(\beta),N(\gamma)>1$ で積が $4,9,6$ のどれかなので、$N(\beta)$ は $2$ か $3$ である。しかし $x^2+5y^2$ は $y=0$ なら平方数、$y\ne0$ なら $5$ 以上なので、$2$ にも $3$ にもならない。よって 4 つの元はどれもそれ以上分解できない（既約元である）。
単元倍で移り合う元（同伴な元）はノルムが等しい。ノルム $4$ の $2$ は、ノルム $6$ の $1\pm\sqrt{-5}$ のどちらとも同伴でない。
したがって $6$ は既約元の積として、単元倍と順序の違いを除いても 2 通りに書ける。$2$ は $(1+\sqrt{-5})(1-\sqrt{-5})=6$ を割り切るが、$(1\pm\sqrt{-5})/2\notin\mathbb{Z}[\sqrt{-5}]$ なので $1+\sqrt{-5}$ も $1-\sqrt{-5}$ も割り切らない。この環は整域であることを満たし、一意分解整域であることを満たさない。破れるのは「整数を含む整域では素因数分解が一意である」という含意である（Ste17 Remark 1.1.7、p. 3）。

性質

存在と一意性

素因数分解の存在と一意性

$2$ 以上の整数は素数の積として書け、その書き方は因子の順序を除いてただ 1 通りである。したがって $2$ 以上の整数の標準形はただ 1 つである。

最小の反例を考える

これは素数の記事の定理「算術の基本定理」であり、完全な証明は同記事にある。要点だけを述べる。
存在：分解できない $2$ 以上の整数があるとして、その最小のものを $n$ とする。$n$ は素数ではない（素数は 1 個の素数の積）ので $n=ab$、$1< a,b< n$ と書け、最小性から $a,b$ は分解できる。それらを並べると $n$ の分解になり、矛盾である。
一意性：2 通りの分解をもつ最小の $n$ を $p_1\cdots p_r=q_1\cdots q_s$ とする。$p_1$ は右辺を割り切るので、素数の記事の系「有限個の積を割り切る素数」によりある $q_j$ を割り切り、$q_j$ は素数なので $p_1=q_j$ である。両辺を $p_1$ で割ると $n/p_1< n$ の 2 通りの分解が得られ（$r=1$ または $s=1$ のときは両辺が $1$ になって $r=s=1$ となる）、最小性に反する。$\square$

一意性の鍵は、素数 $p$ が積 $ab$ を割り切るなら $a$ か $b$ を割り切るという性質（素数の記事の補題「Euclidの補題」）であり、これは Bézoutの等式を通して足し算と掛け算の両方を使って示される。ex-pfac-even と ex-pfac-sqrt-minus-5 は、この性質が失われると一意性も失われることを示している。同じ証明は Ham の Theorem 10.1（p. 192）、Ste17 の Theorem 1.1.6（言明は p. 3、証明は §1.1.4、p. 10）、Sho08 の Theorem 1.3（言明は p. 2、証明は p. 3 と p. 8）にある。

指数の計算規則

$p$ 進付値の性質

$p$ を素数、$a,b$ を $0$ でない整数とする。

$a$ を割り切る $p$ の冪 $p^e$（$e\ge0$）のうち最大のものは $p^{v_p(a)}$ である。
$v_p(ab)=v_p(a)+v_p(b)$ である。
$a+b\neq0$ なら $v_p(a+b)\ge\min(v_p(a),v_p(b))$ である。
$v_p(a)\neq v_p(b)$ なら $a+b\ne0$ であり、$v_p(a+b)=\min(v_p(a),v_p(b))$ である。

分解を並べて比べる

符号は $v_p$ にも割り切る関係にも影響しないので、1 と 2 では $a,b>0$ としてよい。
2. $a$ と $b$ の素因数分解を並べると $ab$ の素因数分解になる。thm-pfac-fta によりこれが $ab$ のただ 1 つの分解なので、その中の $p$ の個数 $v_p(ab)$ は $v_p(a)+v_p(b)$ に等しい。

$e:=v_p(a)$ とし、$a=p^ec$ と書くと $v_p(c)=0$ である。$p^e\mid a$ は明らかである。$p^{e+1}\mid a$ とすると $a=p^{e+1}d$（$d\ge1$）となり、2 により $e=v_p(a)=e+1+v_p(d)\ge e+1$ となって矛盾する。$f\le e$ なら $p^f\mid p^e\mid a$、$f>e$ なら $p^{e+1}\mid p^f$ なので $p^f\nmid a$ である。
$m:=\min(v_p(a),v_p(b))$ とおくと、1 により $p^m$ は $a$ と $b$ を割り切り、したがって $a+b$ を割り切る。1 により $v_p(a+b)\ge m$ である。
$v_p(a)< v_p(b)$ としてよく、$m=v_p(a)$ である。$a+b=0$ なら $b=-a$ で $v_p(b)=v_p(a)$ となるので $a+b\ne0$ である。$v_p(a+b)>m$ とすると $p^{m+1}$ は $a+b$ と $b$（$v_p(b)\ge m+1$）を割り切るので、その差 $a$ を割り切り、1 により $v_p(a)\ge m+1$ となって矛盾する。3 と合わせて $v_p(a+b)=m$ である。$\square$

2 は、$v_p$ が掛け算を足し算に変えること、すなわち対数と同じ働きをすることを言っている。3 の等号は $v_p(a)=v_p(b)$ のとき成り立つとは限らない。$v_2(12)=v_2(20)=2$ だが $v_2(12+20)=v_2(32)=5$ である。一方 $v_2(12)=2\ne3=v_2(8)$ なので $v_2(12+8)=v_2(20)=2$ となり、4 のとおり小さいほうに等しい（3 と 4 は Sho08 Exercise 1.29、p. 13 で演習とされている）。
2 と thm-pfac-fta から、正の整数 $d$ が正の整数 $n$ を割り切ることは、すべての素数 $p$ について $v_p(d)\le v_p(n)$ であることと同値である（最大公約数の記事の定理「素因数分解による最大公約数と最小公倍数」の 1）。同じ定理の 2 により、$\gcd(a,b)$ と $\operatorname{lcm}(a,b)$ の指数は $a,b$ の指数の最小と最大である。約数の個数と総和の公式は約数の記事にある。

有理数の素因数分解

分数も素因数分解できる。$0$ でない有理数 $r=a/b$（$a,b$ は $0$ でない整数）に対して $v_p(r):=v_p(a)-v_p(b)$ と定める。$a/b=c/d$ なら $ad=bc$ なので、prop-pfac-valuation の 2 により $v_p(a)+v_p(d)=v_p(b)+v_p(c)$ であり、$v_p(r)$ は分数の表し方によらない。たとえば $v_2(45/28)=-2$、$v_3(45/28)=2$、$v_5(45/28)=1$、$v_7(45/28)=-1$ である。

有理数の素因数分解

$0$ でない有理数 $r$ は、有限個を除いて $0$ である整数 $e_p$（$p$ は素数全体を動く）によって
$$ r=\pm\prod_pp^{e_p} $$
と書け、このとき符号は $r$ の符号、指数は $e_p=v_p(r)$ であって、この表示はただ 1 通りである。さらに、$r$ が整数であることと、すべての素数 $p$ について $v_p(r)\ge0$ であることは同値である。

分母を払って整数の場合に戻す

存在：$r=a/b$ と書き、$|a|=\prod_pp^{v_p(a)}$、$|b|=\prod_pp^{v_p(b)}$ を割ると $|r|=\prod_pp^{v_p(a)-v_p(b)}$ である。
一意性：$\prod_pp^{e_p}=\prod_pp^{f_p}$（どちらも有限個を除いて指数 $0$）とする。$g_p:=\max(0,-e_p)+\max(0,-f_p)$ とおくと $g_p$ は有限個を除いて $0$ で、$e_p+g_p\ge0$、$f_p+g_p\ge0$ である。両辺に正の整数 $\prod_pp^{g_p}$ を掛けると、正の整数の等式 $\prod_pp^{e_p+g_p}=\prod_pp^{f_p+g_p}$ を得る。thm-pfac-fta により指数は等しく、$e_p=f_p$ である。$e_p=v_p(r)$ は存在の部分で作った表示と一意性からわかる。
整数の判定：$r$ が整数なら $v_p(r)\ge0$ は定義から明らかである。逆にすべての $v_p(r)\ge0$ なら、$\pm\prod_pp^{v_p(r)}$ は整数の積なので整数である。$\square$

$v_p(r)>0$ の素数は $r$ を既約分数で書いたときの分子に、$v_p(r)<0$ の素数は分母に現れる。正の有理数全体は掛け算について、素数を「基底」とする指数の組と 1 対 1 に対応する。

冪であることの判定

冪の判定

$k\ge1$ を整数とする。

正の有理数 $r$ がある正の有理数の $k$ 乗であることと、すべての素数 $p$ について $k\mid v_p(r)$ であることは同値である。
正の整数 $n$ がある有理数の $k$ 乗なら、$n$ はある正の整数の $k$ 乗である。したがって、$n$ が整数の $k$ 乗でなければ $\sqrt[k]{n}$ は無理数である。

指数を $k$ で割る

$r=s^k$（$s>0$ は有理数）なら、prop-pfac-valuation の 2 を分子と分母に使って $v_p(r)=kv_p(s)$ である。逆にすべての $p$ で $v_p(r)=kf_p$ となる整数 $f_p$ があれば、$s:=\prod_pp^{f_p}$ は正の有理数で $s^k=r$ である。
$n=s^k$（$s$ は有理数）なら $|s|^k=n$ なので $s>0$ としてよい。$v_p(s)=v_p(n)/k\ge0$ がすべての $p$ で成り立つので、thm-pfac-rational により $s$ は整数である。$\sqrt[k]{n}$ が有理数なら、それは $n$ の $k$ 乗根となる正の有理数なので整数であり、$n$ は整数の $k$ 乗になる。$\square$

たとえば $v_2(2)=1$ は $2$ でも $3$ でも割り切れないので、$\sqrt2$ も $\sqrt[3]2$ も無理数である。$v_2(12)=2$、$v_3(12)=1$ なので $\sqrt{12}$ は無理数であり、$v_2(72)=3$、$v_3(72)=2$ なので $72$ は平方数でも立方数でもない。同じ事実の別の証明は無理数の記事の定理「冪根の無理性」と平方数の記事の命題「素因数の指数による特徴づけ」にある。指数が整数であることから、$2^a=3^b$ となる正の整数 $a,b$ もない（左辺の $v_2$ は $a\ge1$、右辺は $0$）。これは $\log_23$ が無理数であることを意味する。

平方因子と平方部分

整数 $n\ge1$ が、$1$ 以外のどの平方数でも割り切れないとき、$n$ は 平方因子をもたない（squarefree）という。prop-pfac-valuation の 1 により、これはすべての素数 $p$ で $v_p(n)\le1$ であること、すなわち $n$ が相異なる素数の積（または $1$）であることと同値である。

平方因子をもたない部分と平方の部分への分解

正の整数 $n$ は、平方因子をもたない正の整数 $s$ と正の整数 $m$ によって $n=sm^2$ とただ 1 通りに書ける。

指数を 2 で割った余り

各素数 $p$ について $v_p(n)=2q_p+r_p$（$q_p\ge0$、$r_p\in\{0,1\}$）と書き、$s:=\prod_pp^{r_p}$、$m:=\prod_pp^{q_p}$ とおくと、$s$ は平方因子をもたず $sm^2=n$ である。
逆に $n=sm^2$（$s$ は平方因子をもたない）とすると、prop-pfac-valuation の 2 により $v_p(n)=v_p(s)+2v_p(m)$、$v_p(s)\in\{0,1\}$ なので、$v_p(s)$ は $v_p(n)$ を $2$ で割った余りに等しい。よって $s$ は $n$ から決まり、$m^2=n/s$、$m>0$ から $m$ も決まる。$\square$

たとえば $360=10\cdot6^2$、$72=2\cdot6^2$、$1001=1001\cdot1^2$ である。$n$ が平方数であることは $s=1$ であることと同値であり、$\sqrt n=m\sqrt s$ と平方根を簡単にする操作はこの分解にほかならない。

試し割り

素因数分解を実際に求める最も素朴な方法は、小さい数から順に割ってみることである。次の手順を 試し割り（trial division）という。

$m:=n$、$d:=2$、記録する列を空にする。
$d^2\le m$ である間、次を繰り返す：$d\mid m$ なら $d$ を記録して $m:=m/d$ とし、$d\nmid m$ なら $d:=d+1$ とする。
$d^2>m$ となったら、$m>1$ なら $m$ を記録して終わる。

試し割りの正しさ

$n\ge2$ に試し割りを行うと、手順は有限回で終わり、記録された数を順に並べたものは $n$ の素因数分解（小さい順）である。特に、$2$ 以上 $\sqrt n$ 以下のどの整数でも割り切れない $n\ge2$ は素数である。

手順の途中で保たれる性質

手順 2 の各段階で次の 3 つが成り立つことを、段階の数についての帰納法で示す。(a) $n$ は記録された数の積と $m$ の積に等しい。(b) $m$ は $2$ 以上 $d$ 未満のどの整数でも割り切れない。(c) 記録された数はすべて素数で、記録された順に小さい順（等号を許す）に並び、どれも $d$ 以下である。
最初は記録が空、$m=n$、$d=2$ なので成り立つ。$d\nmid m$ で $d$ を $d+1$ に増やす段階では、(b) の範囲に $d$ が加わるが $d\nmid m$ なので (b) は保たれ、(a)(c) も保たれる。$d\mid m$ の段階では、まず $d$ は素数である。$d$ が合成数なら素因数 $q< d$ をもち、$q\mid d\mid m$ となって (b) に反するからである。$d$ を記録して $m$ を $m/d$ に替えると (a) は保たれ、$m/d$ の約数は $m$ の約数なので (b) も保たれ、(c) も保たれる（$d$ は変わらない）。
各段階で $m$ が減るか $d$ が増える。$d$ は $d^2\le m\le n$ の範囲で動くので $\sqrt n$ を超えて増えることはなく、$m$ は割られるたびに半分以下になるので、段階の数は有限である。
終わったとき $d^2>m$ である。$m\ge2$ なら $m$ は素数である。合成数なら、素数の記事の命題「素因数の存在」の 2 により $\sqrt m$ 以下の素因数 $q$ をもつが、$q\le\sqrt m< d$ となって (b) に反するからである。さらに (b) により $m$ は $d$ 未満の数で割り切れないので $m\ge d$ であり、(c) の記録のあとに $m$ を付け加えても小さい順である。(a) により、記録された素数の積は $n$ に等しい。最後の主張は、$d$ が $2$ から $\sqrt n$ を超えるまで何も記録されずに進んだ場合であり、このとき $m=n$ が記録される。$\square$

手順 2 で割る数 $d$ を素数だけに限っても結果は同じである（合成数の $d$ で割り切れることは起こらないことを証明の中で示した）。この原理で $N$ 以下の素数をまとめて求める方法が Eratosthenesの篩である。ex-pfac-9991 では $d$ が $2$ から $97$ まで進み、$97$ を記録したあと $m=103<97^2$ で終わった。

素因数分解の計算量

試し割りは最悪の場合、$n$ が大きな素数どうしの積のとき、約 $\sqrt n$ 回の割り算を要する。$n$ が $200$ 桁なら $10^{100}$ 回程度であり、現実的な時間では終わらない。より速い方法（2 次篩法、数体篩法など）も知られているが、$n$ の桁数の多項式で抑えられる時間で任意の整数を分解する古典的な（量子計算機を使わない）方法が存在するかどうかは未解決である。量子計算機については Shor が多項式時間の方法を与えている（Ste17 §1.1.3 の Open Problem 1.1.22 とその直後の解説、p. 8）。一方、与えられた数が素数かどうかの判定は、分解を求めることとは別の問題であり、Agrawal–Kayal–Saxena により桁数の多項式時間で行えることが示されている（Ste17 §2.4、p. 38）。RSA暗号は、大きな 2 つの素数の積を公開しても、その分解は求められないだろうという想定の上に成り立っている（Eulerのφ関数の記事の例「RSA暗号とφ(pq)」）。

補足

他の環での素因数分解

整数での素因数分解の一意性は、「単元倍と順序の違いを除いて既約元への分解がただ 1 通り」という形で一般の整域に拡張され、この性質をもつ整域を一意分解整域という。単項イデアル整域は一意分解整域であり、Gauss整数の環 $\mathbb{Z}[i]$ や、体 $K$ 上の 1 変数多項式環 $K[x]$ はその例である（多項式の既約多項式への分解）。ex-pfac-sqrt-minus-5 は、整数を含む整域でも一意分解が成り立たない例である。代数体の整数環では、元の分解の一意性の代わりにイデアルの素イデアルへの分解の一意性が成り立つ（Dedekind整域）。

歴史と文献

HW60 の第 1 章の注（p. 10）によれば、素因数分解の一意性（同書 Theorem 2、p. 3）は Gauss『Disquisitiones Arithmeticae』（1801）§16 より前には明示的に述べられていないようであり、素数が積を割り切れば因子のどれかを割り切るという Euclid の補題（同書 Theorem 3、p. 3）は Euclid『原論』第 7 巻命題 30 である。Euclid がこの補題まで進みながら一意性そのものを述べなかった事情は同書 §12.5（pp. 181–182）で論じられている。$p$ 進付値 $\nu_p$ の積の公式と、$\nu_p$ を使った約数・最大公約数・最小公倍数の表示は Sho08 §1.3（pp. 10–11）、和の付値の不等式は同 Exercise 1.29（p. 13）にある。$\sqrt[k]n$ が整数でなければ無理数であることは Sho08 の Exercise 1.26（p. 13）にある。