因数分解

数学における**因数分解**（いんすうぶんかい、; 分解、**因子分解**）とは、与えられた数学的対象を、同種の（通常はより小さい、あるいはより単純な）対象（**[[約数|因数]]**〈; **因子**、乗法因子、乗因子〉と呼ばれる）の積として書き表すことを言う。例えば、 は  に、多項式  は  に因数分解される。

因数分解は、除法が自由にできる体系（可除環など）では通常意味を持たない。例えば、実数や複素数では任意の数  は0でない数  を用いて  と表せるため、積による分解は無数に存在する。しかし、有理数や有理関数では、分子と分母を分けて考えることで意味のある因数分解定義できる。 

自然数および整数に関する因数分解は、すでに古代ギリシアので研究されていた。その一つが算術の基本定理であり、｢１を除く任意の自然数は素数の積に因数分解でき、その分解〈素因数分解〉は因数の順序を除いて一意である｣ことが示された。整数の素因数分解は、乗法の｢逆演算｣にあたるが、計算量の観点では乗法に比べ格段に難しい。特に巨大整数の素因数分解は短時間で解けないと考えられており、この困難性がRSA暗号などの公開鍵暗号の安全性の基盤となっている。

多項式の因数分解も古くから研究されてきた。初等代数学では、多項式を因数分解することで多項式の根を求める問題を各因子の根を求める問題に帰着できる。整数係数多項式や体係数多項式の環一意分解環であり、算術の基本定理に対応する｢既約多項式による一意分解｣が成り立つ。特に、複素数係数一変数多項式は、必ず一次式の積に一意に表すことができ、これは代数学の基本定理の一つの表現である。この場合、因数分解は求根アルゴリズムが与えられていれば自由にできる。整数係数多項式の因数分解問題は計算機代数の基本課題の一つであり、有理数係数の場合には、実用的なアルゴリズムが確立している。

一般の抽象代数学においては、一意分解性を持つ可換環は一意分解環 (UFD) と呼ばれる。ある種の数体系、例えば代数体の整数環（代数的整数環）の中には一意分解性を持たないものが存在する。しかし、代数的整数環はいずれもデデキント環であり、任意のイデアルが素イデアルの積に一意的に分解されるという、弱い形での一意分解性を満たす。さらに、任意の非零･非単元が既約元に分解できる（ただしその分解が一意とは限らない）整域はまたは分解整域と呼ばれる。

因数分解という用語は、より広く対象を積の形に表すことを指す場合もある。例えば、写像は全射と単射の合成に標準的に分解でき、これは圏論における射のとして一般例である。また、行列の分解としては、行列を性質の異なる行列の積に表すことがあり、例えば任意の行列は下三角行列、上三角行列、置換行列の積に分解される（LUP分解）。これはガウスの消去法を行列の形で表現したものである。

## 整数の因数分解

与えられた正の整数を、それよりも小さな正の整数の積になおすことを「**因数分解**」といい、因数分解したときに現れる整数を、もとの整数の「**[[因数]]**」あるいは「**[[約数]]**」という。（例:60=10×6, 72=6×6×2など）

ただし、単に「因数（あるいは約数）」と言った場合は、その整数自身および1も含めるのが通例である。それら「正の因数」をそれぞれ -1 倍した「負の因数」を含めることも多い。

また、因数分解のなかでも、因数がすべて素数となるように因数分解することを特に「**[[素因数分解]]**」といい、素因数分解したときに現れる素数を、もとの整数の「**[[素因数]]**」という。（例:60=5×3×2×2, 72=3×3×2×2×2など）

算術の基本定理により、任意の正の整数は一意的な素因数分解を持つ。整数の因数分解アルゴリズムが与えられたとき、そのアルゴリズムを繰り返し適用して、任意の整数をその構成要素である素数にまで分解しきることができる。しかし、非常に巨大な整数に対して効率のよいアルゴリズムは知られていない。

## 多項式の因数分解

因数分解は、方程式や関数について考える上で重要な概念の一つである。たとえば次のように左辺を右辺へ変形することをさす。対して、右辺を左辺へ変形することは**展開**という。
# x^2 - 3x + 2 = (x - 1)(x - 2)
# t^3 - t^2 - 3t + 3 = (t - 1)(t^2 - 3)
# \alpha^3 - 1 = (\alpha - 1)(\alpha^2 + \alpha + 1)
これらの場合、1. では **' &minus; 1 と **' &minus; 2 を、2. では **' &minus; 1 と **'2 &minus; 3 を、3. では &alpha; &minus; 1 と &alpha;2 + &alpha; + 1 をそれぞれ因数と呼ぶ。

係数として用いてよい数の範囲が異なると、因数分解の結果が変わってくる。上の3例はすべて有理数（もしくは整数）の範囲で因数分解を行なったものである。数の範囲を実数まで広げると、2. は更に因数分解が行える。
: t^3 - t^2 - 3t + 3 = (t - 1)(t^2 - 3) = (t - 1)\boldsymbol{(t - \sqrt{3})(t + \sqrt{3})}
さらに数の範囲を複素数まで広げると、3. は更に因数分解が行える。
:\alpha^3 - 1 = (\alpha - 1)(\alpha^2 + \alpha + 1) = (\alpha - 1) \left( \alpha - \frac{ - 1 + \sqrt{3}i }{2} \right) \left( \alpha - \frac{ - 1 - \sqrt{3}i }{2} \right)

代数方程式 **'(**') = 0 に対し、その根を求めることは **'(**') を一次式の積に因数分解することと等価である。しかし、展開は機械的に行う方法があるのに対して、整式を因数分解する統一的な方法はないため、状況に応じて適当な方法を適用する必要がある。

### 共通因数でくくる
全ての項に共通している因数でくくり出す。たとえば 2**'<sup>5</sup> &minus; 5**'4 = **'<sup>4</sup>(2**' &minus; 5) など。

### 解の公式の利用
**[[二次方程式の解の公式]]**により、**'<sup>2</sup> + **' + **' = 0 の解は
:<math>x = \frac{ -b \pm \sqrt{b^2 - 4ac} }{2a}</math>
であるので
:<math>ax^2 + bx + c = a \left( x - \frac{ -b + \sqrt{b^2 - 4ac} }{2a} \right) \left( x - \frac{ -b - \sqrt{b^2 - 4ac} }{2a} \right)</math>
と因数分解される。

例として **'2 &minus; **' &minus; 2 を因数分解することを考える。 **'2 &minus; **' &minus; 2 = 0 の解は
:<math>x = \frac{- ( -1 ) \pm \sqrt{( -1 )^2 - 4\cdot1\cdot( -2 )} }{2\cdot1} = 2, -1</math>
である。よって **'2 &minus; **' &minus; 2 = (**' &minus; 2)(**' + 1) という因数分解の結果を得る。

=== 2数の和と積 ===

(**' &minus; &alpha;)(**' &minus; &beta;) = **'2 &minus; (&alpha; + &beta;)**' + &alpha;&beta; という展開を逆向きに使う。**' の項の係数と定数項から2数を見つける方法である。

例として **'<sup>2</sup> &minus; 5**' + 6 を因数分解することを考える。**' の項の係数が &minus;5 で定数項が 6 なので、和が 5 で積が 6 となる2数を探す。2 と 3 であることが分かるので、**'2 &minus; 5**' + 6 = (**' &minus; 2)(**' &minus; 3) という因数分解の結果を得る。

=== たすきがけ ===
2次式を因数分解するときに用いられる、''たすきがけ''とよばれる方法がある。途中計算に引くバツ印の線を[[たすき]]の背中側から見た姿になぞらえた名前である。**'2 の項の係数の正の約数と定数項の約数を組み合わせて **' の項の係数を作る。

たとえば 6**'2 + **' &minus; 2 を因数分解することを考える。**'2 の項の係数 6 の正の約数と定数項 &minus;2 の約数の組み合わせのうち、次のような組み合わせを選ぶ。

 \begin{matrix} 3 & & 2 & \longrightarrow & 4 \\  & \times & & & \\ 2 & & -1 & \longrightarrow & -3\end{matrix}

この計算で得られた 4 と &minus;3 の和が **' の項の[[係数]]1と等しいので、&times; の上の行の数 3 と 2 を使って 3**' + 2 という式と作り、同様に下の行の数 2 と &minus;1 を使って 2**' &minus; 1 という式を作る。このとき、元の２次式 6**'2 + **' &minus; 2 はこの2つの式をかけ合わせることで求められるので、6**'2 + **' &minus; 2 = (3**' + 2)(2**' &minus; 1) という因数分解の結果を得る。

=== 因数定理の利用 ===

因数定理を利用する。すなわち **'(**') の値を 0 にする **' の値（根）を見つける。**'(&alpha;) = 0 となったとすれば、**' &minus; &alpha; が **'(**') の因数の1つである。

たとえば 2**'<sup>4</sup> &minus; 5**'3 &minus; 8**'<sup>2</sup> + 17**' &minus; 6 を因数分解することを考える。この式に **' = 1 を代入すると 0 となるので、**' &minus; 1 が因数の1つであることが分かる。元の式を **' &minus; 1 で[[除算]]して、2**'4 &minus; 5**'<sup>3</sup> &minus; 8**'2 + 17**' &minus; 6 = (**' &minus; 1)(2**'<sup>3</sup> &minus; 3**'2 &minus; 11**' + 6) となる。

この方法で求めた1次の因数以外の因数（この例では 2**'3 &minus; 3**'<sup>2</sup> &minus; 11**' + 6）は、何らかの方法で更に因数分解できるかもしれない。この例では **' = &minus;2 を代入すると 0 になるので **' + 2 も因数だと分かる。

## 因子分解可能な整域
整数の全体  および体  上の多項式環  は一意分解可能&mdash;すなわち「零でも単元でもないすべての元が既約元の積に分解される」（例えば整数の場合には、その単元は  であり、その既約元は素数である）、および「その分解が各因子の並べ替えと因子にいくつかの単元を掛ける違いを除いて一意である」&mdash;という性質を共有している。一意分解可能であるという性質を持つ整域を一意分解整域 (UFD) と呼ぶ。

; 注意: 零でも単元でもない元を「既約元」の積に分解するような因子分解を「既約元分解」と呼び、「素元」の積に分解されるとき「素元分解」と呼ぶ。素元は必ず既約元であったから素元分解は既約元分解の一種であるが、実はその分解は一意である、しかし必ずしも逆（「既約元が必ず素元となる」という性質）は言えないから素元分解でない既約元分解を持つ整域は存在する（これは一意分解可能性質のうち、分解可能よりも一意性の方が困難な性質であることを含意している）。一般に、既約元分解可能な整域は (**AD**)あるいは分解整域 (factorization domain; **FD**) と呼ばれる。一方、「既約元が必ず素元となる」という性質はユークリッドの補題と呼ばれ（これは  の既約元として定義される素数が  の素元であることを述べたユークリッドによる補題に名称を因む）、ユークリッドの補題を満たす整域をEL整域 (ELD) と呼ぶ。明らかに、ELDかつADなる整域において既約元分解は素元分解であり、したがって一意分解である。

UFD において零でも単元でもない任意の元からなる部分集合に対して最大公約元が存在する。逆にそのような任意の部分集合に対して最大公約元を持つ整域は UFD になる。任意の PID は UFD である。

整数の環  と同様のユークリッド除法が定義される整域はユークリッド整域と呼ばれる。任意のユークリッド整域は PID であり、したがって UFD となる。ユークリッド整域において最大公約数の計算に利用できるユークリッドの互除法が定義できるが、それが因数分解アルゴリズムの存在を意味しないことには注意すべきである。適当な体  上の一変数多項式の成すユークリッド環  でその中で一般の多項式に適用可能な因数分解アルゴリズムが無いような  の具体例が存在する。

## イデアルの準素分解

代数的整数論において、ディオファントス方程式の研究の過程で19世紀の数学者は整数を一般化するものとしての代数的整数を導入した。初期に知られた代数的整数環はガウス整数環やアイゼンシュタイン整数環で、これらは通常の整数の場合と同じくPID（したがってUFD）であった。しかし事はそう都合よくはいかず、すぐにほとんどの代数的整数環がPIDでもUFDでもないことが判明する。もっとも簡単な例として、 において 9=3\cdot 3 = (2+\sqrt{-5})(2-\sqrt{-5}) は二通りの既約元分解である。

このように分解の一意性が成り立たないことはディオファントス方程式の解法にとって大きな困難をもたらすものであった。例えば、フェルマーの最終定理に対するかなり多く誤った証明が分解の一意性を暗に仮定したことによる誤りを犯していたのである（「真に驚くべき証明を発見したが、この余白はそれを記すには狭すぎる」と書き残したことで知られるピエール・ド・フェルマーもおそらく例外ではあるまい）。この困難を解決したのはリヒャルト・デーデキントで、それは任意の代数的整数環がイデアルの一意な準素分解を持つという形に述べられる。すなわち、これらの環において、任意のイデアルは準素イデアルの積として表され、その分解は因子の順番を除いて一意である。イデアルに関するこの一意分解性質を持つ整域は、こんにちデデキント整域と呼ばれている。デデキント整域は、それを代数的整数論の基礎たらしめる良い性質を多く持つものである。

## 行列の因子分解

行列環は非可換であり、行列の積は一意分解を与えない（すなわち、ひとつの行列をほかの行列の積として書く方法が一般に複数存在する）から、行列の分解は特定の種類の因子からなるものを考えなければ意味を為さない。例えば、LU分解では下三角行列  と上三角行列  の積  としての分解を考えるものである。LU分解は常に可能であるわけでなく、一般には第三の因子として置換行列  を含めたLUP分解を考える。

は二項関係を表現するもので、行列の積が関係の合成に対応する。論理行列の分解を通して関係を分解することは、のような関係の特質 (nature) の輪郭 (profile) を供与するものである。

## 脚注

### 注釈

### 出典

## 関連項目
* 分解
* 算術の基本定理
* 一意分解環
* 素因数分解
* 多項式の因数分解
* 多項式の根
* 平方完成
* 代数学の基本定理
* 
* : 自然数の（加法的）分割の乗法版

## 外部リンク
* 
*