素因数分解
素因数分解
素数の重要な性質は、$0$ 以外のすべての整数が素数の積に分解されることである（$1$ は空積と考え、負の数については符号を付する）。
すべての $2$ 以上の整数は素数の積 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ （$p_1, p_2, \ldots, p_k$ は相異なる素数）に分解される（その整数自身が素数の場合、つまり $k=1, e_1=1$ の場合も含む）。
このように、整数を素数の積に分解することを素因数分解 (prime factorization)という。
$N=2$ は素数なので、$k=1, p_1=2, e_1=1$ とおくことで$1$つの素数の積に分解される。
$2\leq m\leq N-1$ となる整数 $m$ がすべて素数の積に分解されるとする。
$N$ が素数ならば $k=1, p_1=N, e_1=1$ とおくことで$1$つの素数の積に分解される。
$N$ が合成数ならば
前ページの定理2
より $N$ は素因数 $p$ をもつ。
$N$ は合成数だから $2\leq N/p\leq N-1$ なので、仮定より $N/p$ は素数の積に分解される。
よって $N=p\times (N/p)$ も素数の積に分解される。
よって数学的帰納法より、すべての $2$ 以上の整数は素数の積に分解される。
$1$ については $k=0$ とおくことで、$0$個の素数の積に分解されるとみることができる。
また負の数 $-N$ については、$N$ の素因数分解 $N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ に対して、$-N=-p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ を $-N$ の素因数分解とみることで、$0$ 以外のすべての整数は素因数分解されると考えることができる。
しかし、素因数分解が存在することと、実際に与えられた整数の素因数分解を求めることができるかどうかは別の問題である。大きな整数の素因数分解を求めることは現時点では難しい問題である。
なお、ここでは素因数分解が存在することを示したが、さらに、整数の素因数分解は順序を除いて一意的であることを、 倍数と約数の記事で示した形の初等整数論の基本定理 を用いて 後に示す 。
初等整数論の基本定理
倍数と約数の記事で示した形の初等整数論の基本定理 を用いて、整数の素因数分解は順序を除いて一意的であることを示す（通常は 定理4 を初等整数論の基本定理と呼ぶが、本質的なのは 倍数と約数: 定理5 であり、以下の議論は手続き的な議論である）。
$p$ が $ab$ の素因数ならば $p$ は $a, b$ の少なくとも一方を割り切る。
$p$ が $a$ を割り切らないならば 前ページの定理1 より $\gcd(a, p)=1$ だから、 初等整数論の基本定理 より $p$ は $b$ を割り切る。
$p$ が素数でなければ、このことは一般には成り立たない。実際 $n$ が合成数で $n=ab$ かつ $a>1, b>1$ とおくと、$n$ は $ab$ を割り切るが $a, b$ のどちらも割り切らない。
それで定理4.1は素数であることの必要十分条件を与えている。素因数分解の一意性は素数の定義よりも、この定理からより直接的に従うので、実はこの定理こそが素数の本質をあらわしていると考えることもできる。
実際、一般の環においては、
前頁の定義1
に相当する性質（単元と自分自身以外では割り切れない）と、定理2に相当する性質（$ab$ を割り切るとき $a, b$ の少なくとも一方を割り切る）は必ずしも同値ではない。
前者の性質をもつものを既約元、後者の性質をもつものを素元という。そして素元のほうが素数にあたる性質をもっていることがわかるのである（定理2は整数環 $\Z$ においては、既約元であることと素元であることは同値であることをいっている。しかし、一般の環においては素元の積への分解ができるとは限らない。この問題を解決するのがイデアルの概念である）。
定理4.1は $2$ つの数の積について取り扱っていたが、より多くの個数の数の積へと拡張できる。
$k\geq 2$ で $p$ が $a_1 a_2 \cdots a_k$ の素因数ならば $p$ は $a_i (1\leq i\leq k)$ の少なくとも$1$つを割り切る。
$k=2$ のときは 定理2 そのものである。
$k=n-1$ のときに定理が成り立つとする。$p$ が $a_1 a_2 \cdots a_n$ の素因数ならば
定理2
より $p$ は $a_1 a_2 \cdots a_{n-1}$ または $a_n$ の少なくとも一方を割り切る。$p$ が $a_1 a_2 \cdots a_{n-1}$ を割り切るとき仮定より $p$ は $a_i (1\leq i\leq n-1)$ の少なくとも$1$つを割り切る。
よって、いずれの場合も $p$ は $a_i (1\leq i\leq n)$ の少なくとも$1$つを割り切る。
以上のことから、数学的帰納法より、定理は任意の $k\geq 2$ に対して成り立つ。
$0$ 以外の任意の整数は順序を除いて素数の積に一意的に分解される。
素因数分解が存在することは 定理1 より従う。
$N\neq 0$ が素数の積に
$$\begin{split}
N=& p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \\
N=& q_1^{f_1} q_2^{f_2} \cdots q_\ell^{f_\ell}
\end{split}$$
と分解されているとする。ただし $p_1, p_2, \ldots, p_k$ は相異なる素数、$q_1, q_2, \ldots, q_\ell$ も相異なる素数とし、$e_1, e_2, \ldots, e_k, f_1, f_2, \ldots, f_\ell>0$ とする。
各 $q_s (1\leq s\leq \ell)$ は $N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ を割り切るので、
定理3
より $q_s$ は $p_1, p_2, \ldots, p_k$ の少なくとも$1$つを割り切る。
$q_s$ および $p_1, p_2, \ldots, p_k$ は素数なので
前ページの定理1 (2)
より $q_s$ は $p_1, p_2, \ldots, p_k$ のいずれかと一致する。
同様にして各 $p_t (1\leq t\leq k)$ は $q_1, q_2, \ldots, q_\ell$ のいずれかと一致する。よって $k=\ell$ で、$p_1, p_2, \ldots, p_k$ と $q_1, q_2, \ldots, q_\ell$ は順序を除いて一致する。
$q_s=p_t$ とし、$f_s>e_t$ とすると $q_s^{f_s-e_t}$ は $N/q_s^{e_t}=N/p_t^{e_t}=\prod_{1\leq i\leq k, i\neq t} p_i^{e_i}$ を割り切るから
$q_s=p_t$ は $\prod_{1\leq i\leq k, i\neq t} p_i^{e_i}$ を割り切る。よって
定理3
と
前ページの定理1 (2)
より $p_t$ は $p_i (1\leq i\leq k, i\neq t)$ のいずれかと一致するが、
$p_1, p_2, \ldots, p_k$ は相異なる素数となるようにとったことに矛盾する。よって $f_s\leq e_t$ である。同様に $e_t\leq f_s$ もいえるから
$f_s=e_t$ でなければならない。
以上より、$p_1^{e_1}, p_2^{e_2}, \ldots, p_k^{f_k}$ と $q_1^{f_1}, q_2^{f_2}, \ldots, q_\ell^{f_\ell}$ は順序を除いて一致する。
よって $N$ は順序を除いて素数の積に一意的に分解される。
素因数分解の一意性の応用
素因数分解の一意性から、与えられた整数の約数は素因数によって決定されることがわかる。すなわち
$N=\pm p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ と素因数分解すると、
$$d\mid N \Leftrightarrow d=\pm p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}, f_i\in\Z, 0\leq f_i\leq e_i (1\leq i\leq k)$$
$$\pm d=p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}, f_i\in\Z, 0\leq f_i\leq e_i (1\leq i\leq k)$$
ならば
$$N=\pm d p_1^{e_1f_1} p_2^{e_2-f_2} \cdots p_k^{e_k-f_k}$$
となるから、$d$ は $N$ の約数である（この証明において、$\pm$ のさす符号は必ずしも一致しない）。
$d$ が $N$ の約数とし $N=dm$ とおいて
$$d=\pm q_1^{g_1} q_2^{g_2} \cdots q_\ell^{g_\ell}, m=\pm q_1^{h_1} q_2^{h_q} \cdots q_\ell^{h_\ell}, g_i, h_i\in\Z, g_i, h_i\geq 0$$
と素因数分解すると
$$N=dm=\pm q_1^{g_1+h_1} q_2^{g_2+h_2} \cdots q_\ell^{g_\ell+h_\ell}$$
となるが、
素因数分解の一意性
から、
各 $j$ に対して $q_j=p_i, g_j+h_j=e_i$ となる $i$ が$1$対$1$に対応する。よって
$p_i=q_j$ となる $i$ に対して $f_i=g_j$ とおくと
$$d=\pm p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}, f_i\in\Z, 0\leq f_i\leq e_i (1\leq i\leq k)$$
となる。
素数 $p$ と $0$ ではない整数 $N$ について $v_p(N)$ を、$p$ が $N$ を割り切る回数、つまり $p^e\mid N$ となる最大の整数 $e$ とする。このとき
- $e=v_p(N)$ $\Longleftrightarrow$ $N=p^e M$, $p\not\mid M$ となる整数 $M$ が存在する。
- $0$ でない、任意の整数 $a, b$ について、$v_p(ab)=v_p(a)+v_p(b)$.
- $a, b$ が $0$ ではない整数で、$v_p(a)\neq v_p(b)$ のとき $v_p(a+b)=\min\{v_p(a), v_p(b)\}$.
- $e=v_p(N)$ とおくと、$p^e\mid N$ となるから、$N=p^e M$ となる整数 $M$ が存在する。$p\mid M$ のとき $p^{e+1}\mid N$ となって矛盾するから、
$p$ は $M$ を割り切らない。逆に $N=p^e M$ かつ $p\not\mid M$ とすると、$p^e$ は $N$ を割り切る。しかし $N=p^{e+1} L$ となる整数 $L$ が存在するとすると
$M=pL$ となって矛盾するから $p^{e+1}$ は $N$ を割り切らない。よって $v_p(N)=e$ となる。 - $e=v_p(a)$, $f=v_p(b)$ とおくと、$a=p^e s$, $b=p^f t$ となる整数 $s, t$ が存在して、$p$ は $s$, $t$ のいずれも割り切らない。よって
初等整数論の基本定理2 より、$p$ は $st$ を割り切らない。$ab=p^{e+f} st$ であるから、$v_p(ab)=e+f$ となる。 - $e=v_p(a)$, $f=v_p(b)$ とおく。$e>f$ と仮定しても一般性を失わない。さらに $a=p^e s$, $b=p^f t$ となる整数 $s, t$ が存在して、$p$ は $s$, $t$ のいずれも割り切らない。$$a+b=p^e s+p^f t=p^f(p^{e-f}s+t)$$となるが、
$e-f>0$ で、$p$ は $t$ を割り切らないので、$p$ は $p^{e-f}s+t$ を割り切らない。よって $$v_p(a+b)=f=\min\{v_p(a), v_p(b)\}$$ となる。
階乗や二項係数の素因数分解について、次のことが示される。
$m\geq 0$ のとき $$v_p(m!)=\sum_{i=1}^\infty \floor{\frac{m}{p^i}}.$$
$1$ 以上 $m$ 以下の整数であって $p^i$ の倍数であるようなものの個数は $\floor{\frac{m}{p^i}}$ 個である。よって、 定理6の2 より $v_p(m!)$ は $$\sum_{i=1}^\infty \floor{\frac{m}{p^i}}$$ と求まる。ただし、この無限和について、実際には有限個の項を除いては $0$ と等しいため、実質的に有限和を表しているものと考える。
このことから、次のことがすぐにわかる。
$n\geq 0$, $0\leq k\leq n$ のとき $$v_p\left(\binom{n}{k}\right)=\sum_{e=1}^{\infty} \left(\floor{\frac{n}{p^e}}-\floor{\frac{k}{p^e}}-\floor{\frac{n-k}{p^e}}\right).$$
実数 $r$ と $s$ について $\floor{r}+\floor{s}\leq \floor{r+s}$ が成り立つので、このことは二項係数の値がつねに整数であることの別証明を与えている。
参考文献
