素因数

同義語:prime factor

概要

素因数(prime factor)とは、$0$ でない整数 $n$ を割り切る素数のことで、$p^e\mid n$ となる最大の $e$($p$ 進付値 $v_p(n)$)をその重複度という。たとえば $360=2^3\cdot3^2\cdot5$ の素因数は $2,3,5$ である。素因数の集合は積で和集合に、最大公約数で共通部分になり、$a$ の素因数がすべて $b$ の素因数であることは、ある $k$ について $a\mid b^k$ となることと同値である。決まった $k$ 個の素数だけを素因数にもつ $x$ 以下の数は $(1+\log_2x)^k$ 個以下しかなく、定数でない整数係数多項式の値には無限に多くの素数が素因数として現れる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 素数, 約数, 素因数分解

$360=2^3\cdot3^2\cdot5$ を割り切る素数は $2,3,5$ の 3 つである。これらを $360$ の 素因数(prime factor)といい、$2$ は $3$ 回、$3$ は $2$ 回、$5$ は $1$ 回現れる。ある数がどの素数で割り切れるかは、偶奇($2$ で割り切れるか)や、互いに素かどうか(共通の素因数がないか)のように、整数の性質を述べるときにいちばんよく使われる情報である。
素因数の定義と、指数 $v_p(n)$ の計算規則は 素因数分解 の記事にある。この記事では、素因数の 集合 に注目する。積・最大公約数・冪をとると素因数の集合がどう変わるか(prop-pf-set)、決まった有限個の素数だけを素因数にもつ数がどれほど少ないか(thm-pf-finite-set)、整数係数の多項式の値に現れる素因数が無限に多いこと(thm-pf-polynomial)を証明し、整数以外の環での素因数に触れる。

結果内容
prop-pf-set積・最大公約数・冪と素因数の集合
thm-pf-finite-set$k$ 個の素数だけを素因数にもつ $x$ 以下の数は $(1+\log_2x)^k$ 個以下
thm-pf-polynomial定数でない整数係数多項式の値には無限に多くの素数が素因数として現れる

定義

素因数と重複度

$n$ を $0$ でない整数とする。$n$ を割り切る素数 $p$ を $n$ の 素因数 という。$p$ が $n$ の素因数のとき、$p^e\mid n$ となる最大の $e\ge1$、すなわち p進付値 $v_p(n)$ を $p$ の 重複度(または指数)という。$n$ の素因数全体の集合を $\mathcal P(n)$ と書く。$\lvert n\rvert\ge2$ のとき、$\mathcal P(n)$ の最小の元と最大の元を $n$ の 最小素因数、最大素因数 といい、$p^-(n)$、$P^+(n)$ と書く。

$v_p$ の定義と性質は 素因数分解 の記事の定義「素因数ごとの指数」と命題「$p$ 進付値の性質」のとおりで、$\mathcal P(n)=\{p\mid v_p(n)\ge1\}$ である。$\mathcal P(n)$ の元の個数は $\omega(n)$、重複度を込めた個数 $\sum_pv_p(n)$ は $\Omega(n)$ と書かれる(素因数の個数)。$\mathcal P(n)$ の元の積は $n$ の 根基 $\operatorname{rad}(n)$ である(abc予想 の定義「根基」)。

  • $n=\pm1$ には素因数がない($\mathcal P(\pm1)=\emptyset$)。$0$ はすべての素数で割り切れるので、素因数の議論では除いておく。
  • $n$ と $-n$ の素因数と重複度は同じである。
  • 代数体の整数環などでは、素イデアルの因子を「素因子」と呼ぶことが多い。代数幾何学の「素因子」(prime divisor)は余次元 1 の既約閉部分多様体のことで、別の概念である。
小さな数の素因数
$n$標準形$\mathcal P(n)$$p^-(n)$$P^+(n)$$\operatorname{rad}(n)$$\omega(n)$$\Omega(n)$
$360$$2^3\cdot3^2\cdot5$$\{2,3,5\}$$2$$5$$30$$3$$6$
$97$$97$$\{97\}$$97$$97$$97$$1$$1$
$1001$$7\cdot11\cdot13$$\{7,11,13\}$$7$$13$$1001$$3$$3$
$1024$$2^{10}$$\{2\}$$2$$2$$2$$1$$10$
$12$$2^2\cdot3$$\{2,3\}$$2$$3$$6$$2$$3$
$18$$2\cdot3^2$$\{2,3\}$$2$$3$$6$$2$$3$

$12$ と $18$ は素因数の集合も $\Omega$ も同じだが、重複度の並び方が違う。素因数の集合だけでは数は決まらない。

素因数の集合の性質

積・最大公約数・冪と素因数の集合

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

  1. $\lvert a\rvert\ge2$ なら $\mathcal P(a)$ は空でない有限集合で、$p^-(a)$ は $\lvert a\rvert$ の $1$ より大きい最小の約数である。$\lvert a\rvert$ が合成数なら $p^-(a)\le\sqrt{\lvert a\rvert}$ である。
  2. $\mathcal P(ab)=\mathcal P(a)\cup\mathcal P(b)$ であり、$k\ge1$ について $\mathcal P(a^k)=\mathcal P(a)$ である。
  3. $\mathcal P(\gcd(a,b))=\mathcal P(a)\cap\mathcal P(b)$ である。とくに、$a$ と $b$ が互いに素であることと、共通の素因数をもたないことは同値である。
  4. $\mathcal P(a)\subset\mathcal P(b)$ であることと、ある $k\ge1$ について $a\mid b^k$ であることは同値である。
  5. $\mathcal P(a)=\mathcal P(b)$ であることと、$\operatorname{rad}(a)=\operatorname{rad}(b)$ であることは同値である。
Euclid の補題と指数の比較

1:$\mathcal P(a)$ は $\lvert a\rvert$ 以下の数からなるので有限である。残りは 素数 の記事の命題「素因数の存在」である。
2:Euclidの補題 の定理「Euclidの補題」により、素数 $p$ について $p\mid ab$ と「$p\mid a$ または $p\mid b$」は同値である。$a^k=a\cdot a^{k-1}$ にこれを繰り返し使えば $\mathcal P(a^k)=\mathcal P(a)$ を得る。
3:$d=\gcd(a,b)$ は $a$ と $b$ を割り切り、$a,b$ の公約数はすべて $d$ を割り切る(最大公約数)。よって素数 $p$ について、$p\mid d$ と「$p\mid a$ かつ $p\mid b$」は同値である。$\gcd(a,b)=1$ は $\mathcal P(\gcd(a,b))=\emptyset$ と同値である(1 による)。
4:$a\mid b^k$ なら、2 により $\mathcal P(a)\subset\mathcal P(b^k)=\mathcal P(b)$ である。逆に $\mathcal P(a)\subset\mathcal P(b)$ とし、$k:=\max(\{1\}\cup\{v_p(a)\mid p\in\mathcal P(a)\})$ とおく。$p\in\mathcal P(a)$ なら $v_p(b)\ge1$ なので $v_p(b^k)=kv_p(b)\ge k\ge v_p(a)$ であり、$p\notin\mathcal P(a)$ なら $v_p(a)=0\le v_p(b^k)$ である。すべての素数 $p$ で $v_p(a)\le v_p(b^k)$ なので、$a\mid b^k$ である(最大公約数 の定理「素因数分解による最大公約数と最小公倍数」の 1)。
5:$\operatorname{rad}(a)=\prod_{p\in\mathcal P(a)}p$ で、素因数分解 の一意性から、相異なる素数の積は素数の集合を決める。$\square$

3 から、連続する 2 整数 $n$ と $n+1$ は共通の素因数をもたない(公約数は差 $1$ を割り切る)。Euclid の素数の無限性の証明は、$2\cdot3\cdots p+1$ の素因数が $p$ 以下のどの素数とも異なることを使う(素数の無限性)。
4 の「ある $k$ について $a\mid b^k$」は、$\mathcal P(a)\subset\mathcal P(b)$ を割り算の言葉で言い換えたものである。たとえば $\mathcal P(12)=\{2,3\}\subset\{2,3\}=\mathcal P(18)$ なので $12\mid18^k$ となる $k$ があり、実際 $18^2=324=12\cdot27$ である。$k=1$ では足りない($12\nmid18$)。

決まった素数だけを素因数にもつ数

素因数をある有限集合の中に限ると、そのような数はまばらにしかない。

有限個の素数だけを素因数にもつ数の個数

$S$ を $k$ 個の素数からなる集合とし、$x\ge1$ とする。$\mathcal P(n)\subset S$ となる $x$ 以下の正の整数 $n$ の個数は、$(1+\log_2x)^k$ 以下である。

指数の組を数える

$\mathcal P(n)\subset S$ となる正の整数 $n$ は、$n=\prod_{p\in S}p^{e_p}$($e_p\ge0$)とただ 1 通りに書ける(素因数分解)。$n\le x$ なら、各 $p\in S$ について $2^{e_p}\le p^{e_p}\le n\le x$ なので $0\le e_p\le\log_2x$ であり、$e_p$ のとりうる値は $1+\lfloor\log_2x\rfloor$ 個以下である。$n$ は指数の組 $(e_p)_{p\in S}$ で決まるので、$n$ の個数は $(1+\log_2x)^k$ 以下である。$\square$

$k$ を固定すると $(1+\log_2x)^k/x\to0$($x\to\infty$)なので、十分大きい $x$ では $x$ 以下の正の整数のほとんどが $S$ の外に素因数をもつ。とくに $S$ をどの有限集合にとっても $S$ の外に素数があり、素数は無限に多い。これは 素数の無限性 の別証明である。$S$ が最初の $k$ 個の素数の場合には、$n$ を平方因子をもたない数と平方数の積に分けて数えることで、個数が $2^k\sqrt x$ 以下という別の評価が得られる($k$ を固定して $x\to\infty$ とすると上の評価のほうが小さく、$k$ が大きいとこちらが小さい。$x=100$、$k=2$ では $40< 58.4$)(HW60 §2.6、pp. 16–17)。

2 と 3 だけを素因数にもつ数

$S=\{2,3\}$、$x=100$ とする。$\mathcal P(n)\subset\{2,3\}$ となる $100$ 以下の正の整数は
$$ 1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96 $$
の $20$ 個で、上界 $(1+\log_2100)^2\approx58.4$ より少ない。$100$ 以下の整数の残り $80$ 個は、$5$ 以上の素因数をもつ。

有限個の素数の代わりに「$y$ 以下の素数」を考え、$y$ 以下の素因数だけをもつ数を $y$-smooth という。$y$-smooth な数の分布は、素因数分解や離散対数の計算法の解析に使われる(Sho08 §15.1、p. 399)。

多項式の値の素因数

多項式の値の素因数は無限に多い

$f\in\mathbb{Z}[x]$ を定数でない多項式とする。素数 $p$ で、ある整数 $m$ について $f(m)\ne0$ かつ $p\mid f(m)$ となるものは無限に多い。

値を 1 に合同な形にずらす

$f$ は定数でないので、$f(m)=0$ となる整数 $m$ は有限個しかなく、$\lvert f(m)\rvert\to\infty$($\lvert m\rvert\to\infty$)である。
$c:=f(0)=0$ の場合:各素数 $p$ について、$f(x)=xg(x)$($g\in\mathbb{Z}[x]$)なので $p\mid f(pt)$ がすべての整数 $t$ で成り立ち、$f(pt)\ne0$ となる $t$ がある。よってすべての素数が条件を満たす。
$c\ne0$ の場合:条件を満たす素数が有限個 $p_1,\dots,p_r$ しかないとして矛盾を導く($r=0$ も許す)。$Q:=p_1\cdots p_r$($r=0$ なら $Q=1$)とし、$f(x)=c+\sum_{i=1}^da_ix^i$ と書くと
$$ f(cQt)=c\Bigl(1+\sum_{i=1}^da_ic^{i-1}Q^it^i\Bigr)=c\,h(t),\qquad h(t):=1+\sum_{i=1}^da_ic^{i-1}Q^it^i\in\mathbb{Z}[t] $$
である。$h$ は $f$ と同じ次数 $d\ge1$ をもつので、$\lvert h(t)\rvert\ge2$ となる整数 $t$ がある。このとき $h(t)$ の素因数 $q$ をとると、$h(t)\equiv1\pmod Q$ なので $q$ はどの $p_j$ とも異なる。一方 $f(cQt)=c\,h(t)\ne0$ で $q\mid f(cQt)$ なので、$q$ は条件を満たし、矛盾する。$\square$

したがって、$y$ をどれだけ大きくとっても、$P^+(f(m))>y$ となる整数 $m$($f(m)\ne0$)がある。どの素数が実際に現れるかは、$f$ を $p$ を法として見ればわかる:$p$ がある $f(m)$ を割り切ることは、$f$ を $p$ を法として還元した多項式が $\mathbb{F}_p$ に根をもつことと同値である($m$ を $p$ で割った余りが根になる)。

x^2+1 と x^2+x+1 の値の素因数

$f(x)=x^2+1$ の値の素因数は、$2$ と、$4$ で割って $1$ 余る素数全体である。$p$ が奇素数のとき、$p\mid m^2+1$ は $-1$ が $p$ を法とする平方剰余であることと同値で、それは $p\equiv1\pmod4$ と同値だからである(平方剰余 の系「−1 が平方剰余となる素数」。奇素因数が $4$ で割って $1$ 余ることは HW60 Theorem 13、p. 13)。たとえば $m=1,\dots,8$ について $m^2+1=2,5,10,17,26,37,50,65$ で、現れる素因数は $2,5,13,17,37$ である。thm-pf-polynomial と合わせると、$4$ で割って $1$ 余る素数が無限に多いことが従う。
$f(x)=x^2+x+1$ は 3 番目の円分多項式 $\Phi_3$ で、値の素因数は $3$ か $3$ で割って $1$ 余る素数である(円分多項式 の定理「円分多項式の値の素因数」)。

形の決まった数の素因数には、ほかにも合同条件がつくことが多い。Fermat 数 $2^{2^m}+1$ の素因数は $2^{m+1}$ を法として $1$ に合同であり(Fermat数 の命題「Fermat数の素因数の合同条件」)、Mersenne 数 $2^p-1$($p$ は奇素数)の素因数は $2p$ を法として $1$ に合同である(Mersenne素数 の命題「Mersenne数の素因数の合同条件」)。$a^n-1$ には、それより前の $a^m-1$($m< n$)に現れない新しい素因数が、少数の例外を除いて現れる(Zsigmondyの定理)。$n!$ の素因数はちょうど $n$ 以下の素数で、その重複度は 階乗に含まれる素因数の個数 の Legendre の公式で計算できる。

整数以外の環での素因数

一意分解整域 では、$0$ でも単元でもない元 $a$ を割り切る 素元 を $a$ の素因数と呼ぶ。素因数は単元倍(同伴)の違いを除いて決まり、重複度も整数の場合と同様に定まる。

  • Gauss整数 の環 $\mathbb{Z}[i]$ では $5=(2+i)(2-i)$、$2=-i(1+i)^2$ であり、$5$ の素因数は $2+i$ と $2-i$(同伴でない)、$2$ の素因数は $1+i$(重複度 $2$)である。整数としては素数の $5$ が、$\mathbb{Z}[i]$ では 2 つの素因数をもつ。
  • 体 $K$ 上の多項式環 $K[x]$ では、素因数は既約多項式である。$x^4-1$ は $\mathbb{Q}$ 上 $(x-1)(x+1)(x^2+1)$、$\mathbb{C}$ 上 $(x-1)(x+1)(x-i)(x+i)$、$\mathbb{F}_5$ 上 $(x-1)(x-2)(x-3)(x-4)$ と分かれ、素因数の集合は係数の体に依存する(既約多項式)。
  • 一意分解整域でない環では、既約元への分解が一意でないので、素因数とその重複度が元から決まらない(ex-pf-counterexamples の 3 行目)。代数体の整数環では、元の代わりにイデアルを素イデアルに分解し、その素イデアルを素因子と呼ぶ(Dedekind整域、代数体における素イデアルの分解)。

反例

外した条件例成り立たなくなる結論
$\lvert a\rvert\ge2$$a=1$$\mathcal P(a)$ が空でない(prop-pf-set の 1)
$f$ が定数でない$f(x)=6$値の素因数が無限に多い(thm-pf-polynomial)
$f$ が多項式$f(m)=2^m$($m\ge0$)値の素因数が無限に多い(thm-pf-polynomial)
環が一意分解整域$\mathbb{Z}[\sqrt{-5}]$ の $6$既約元の因子とその重複度が元から決まる
反例の確かめ

1 行目:$1$ を割り切る素数はない(素数は $2$ 以上)。
2 行目:値はつねに $6$ で、素因数は $2,3$ の 2 つだけである。
3 行目:$f$ は整数値で定数でなく、値は $0$ にならないが、$2^m$ の素因数は $2$ だけである($m=0$ では素因数なし)。thm-pf-polynomial の証明の、$f(cQt)$ を $c$ と「$Q$ を法として $1$ に合同な数」の積に書く段が、多項式でない $f$ では使えない(実際 $c=f(0)=1$、$Q=2$ で $f(2t)=4^t$ は $2$ を法として $0$ に合同である)。
4 行目:$6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ で、$2,3,1\pm\sqrt{-5}$ はどれも既約元であり、$2$ は $1\pm\sqrt{-5}$ のどちらとも同伴でない(素因数分解 の例「反例:整数を拡げた環での 2 通りの分解」)。$2$ を $6$ の既約因子に数えるかどうかが分解の選び方で変わる。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する