因数分解のソースを表示

{{混同|素因数分解}}
{{出典の明記|date=2016-06}}
[[File:Factorisatie.svg|thumb|right|多項式 {{math|''x''{{exp|2}} + ''cx'' + ''d''}} は、{{math|1=''a'' + ''b'' = ''c''}} および {{math|1=''ab'' = ''d''}} であるとき、{{math|(''x'' + ''a'')(''x'' + ''b'')}} と因数分解できる。]]
[[数学]]における'''因数分解'''（いんすうぶんかい、{{lang-en-short|''factorization'', ''factoring'', ''decomposition''}}{{efn|加法的な体系では和に分解することもあるかもしれない。傾向として、decomposition は加法的な分解（ある種の直和分解など）に対してよく用いられる。}}; [[分解#数学|分解]]、'''因子分解'''）は、与えられた数学的対象を同種の（しかし普通はより小さいあるいはより平易な）別の対象（'''[[約数|因数]]'''〈{{lang|en|''factor''}}; '''因子'''、乗法因子、乗因子〉と呼ばれる）の[[積]]として書き表すことを言う{{efn|「積として」と述べる時点で何らかの意味での「乗法」が定められている必要がある。ただし、一般の抽象的文脈において「乗法」が任意の（代数的）演算を指し得ることや、可換な乗法が「加法」と呼ばれていたりする場合があることには留意すべきである。}}。たとえば、{{math|15}} という数は {{math|3 &times; 5}} という因数の積に分解され、多項式 {{math|''x''<sup>2</sup> &minus; 4}} は {{math|(''x'' &minus; 2)(''x'' + 2)}} という因数の積に分解される。

因子への分解は、[[除法]]が自由にできる体系（[[可除環]]など）ではほとんどの場合に意味を為さない。例えば[[実数]]や[[複素数]]の体系において任意の {{mvar|x}} は {{mvar|y}} が零でない限り何であっても {{math|''xy'' &times; ({{sfrac|1|''y''}})}} のように分解できることは明らかである（つまり、どの元もいくらでも分解できて、積としての表示を無数に持つ）。しかし例えば、[[有理数]]や[[有理関数]]の成す体系ならば、分子と分母を別々に考えることによって意味のある因数分解を定めることができる。 

[[自然数]]および[[整数]]に関する因数分解は[[古代ギリシア]]の{{ill2|ギリシア数学|label=数学|en|Greek mathematics}}においてすでに考察されている。その中には、１を除く任意の自然数が[[素数]]の積に因数分解できる（さらに、自然数のそのような分解〈[[素因数分解]]〉は因数の順番を変える[[違いを除いて]]一通りである）ことを述べた[[算術の基本定理]]の証明も含まれる。整数の素因数分解は、整数の乗法のある種の逆演算ではあるけれども、しかし[[アルゴリズム]]的な意味（[[計算量]]）において乗法とは比べ物にならないほど複雑であり、特に巨大整数の素因数分解は困難な問題で、これを一般に短時間に行う方法は知られていない。この複雑性は[[RSA暗号]]のような[[公開鍵暗号]]によるセキュリティの信頼性の基礎になっている。

[[多項式の因数分解]]もまた何世紀にもわたって研究がおこなわれてきている。[[初等代数学]]においては、多項式を因数分解することで[[多項式の根]]を求める求根問題を各因子の根を求める問題に帰着させることができる。整数係数の多項式あるいは[[可換体|体]]に係数をとる多項式の体系は[[一意分解環|一意分解性質]]を備えている&mdash;それはつまり、（素数を既約多項式に取り換えた）算術の基本定理の多項式版が成り立つということである&mdash;。特に、[[複素数]]係数の[[一変数多項式]]は、必ず[[一次多項式|一次式]]の積に（掛ける順番を除いて）一意に表すことができる&mdash;これは[[代数学の基本定理]]の一つの述べ方である&mdash;。この場合、因数分解は[[求根アルゴリズム]]が与えられていれば自由にできる。整数係数の場合の多項式の因数分解問題は[[計算機代数]]においてひとつの基礎を成す技術的課題である。有理数係数の多項式環における既約因子分解には、効果的な計算機アルゴリズムが存在している。

一般の[[抽象代数学]]において、一意分解性質を持つ[[可換環]]は[[一意分解環]] (UFD) と呼ばれる。ある種の[[数体系]]、例えば[[代数体]]の[[整数環]]（代数的整数環）の中には一意分解性質を持たないものが存在するが、これら代数的整数環の場合には幸いなことに、より弱い形での一意分解性質（任意の[[イデアル (環論)|イデアル]]が[[素イデアル]]の積に一意的に分解される）を満足する[[デデキント環]]となる。一般に、既約元分解を持つ（が、一意分解とは限らない）[[整域]]を{{ill2|原子整域|en|atomic domain}}または分解整域と呼ぶ。

より一般の数学的対象の中にも（より単純な対象からなる）積の形に書き表すことを一般に因子分解あるいは分解と言い表すものがある。たとえば、[[写像]]の分解とは特定の性質を持つ写像の[[写像の合成|合成]]の形に書き表すことである。任意の写像は[[全射]]と[[単射]]の合成として標準的な分解を持つ（これは[[圏論]]において、射の{{仮リンク|分解系 (圏論)|en|factorization system|label=分解系・弱分解系}}として一般化される）。また例えば、[[行列の分解]]とは、与えられた[[行列]]を特定の性質を持つ行列を用いて[[行列の積]]として書き表すことである。任意の行列は対角成分がすべて {{math|1}} の[[下三角行列]] {{mvar|L}} と[[上三角行列]] {{mvar|U}} および [[置換行列]] {{mvar|P}} の積に分解される（[[LU分解|LUP分解]]: 実はこれは[[ガウスの消去法]]を行列の形にまとめたものである）。

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

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

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

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

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

[[係数]]として用いてよい[[数]]の範囲が異なると、因数分解の結果が変わってくる。上の3例はすべて[[有理数]]（もしくは[[整数]]）の範囲で因数分解を行なったものである。数の範囲を[[実数]]まで広げると、2. は更に因数分解が行える。
: <math>t^3 - t^2 - 3t + 3 = (t - 1)(t^2 - 3) = (t - 1)\boldsymbol{(t - \sqrt{3})(t + \sqrt{3})}</math>
さらに数の範囲を[[複素数]]まで広げると、3. は更に因数分解が行える。
:<math>\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)</math>
<br>
[[代数方程式]] ''{{Mvar|f}}''(''{{Mvar|x}}'') = 0 に対し、その根を求めることは ''{{Mvar|f}}''(''{{Mvar|x}}'') を一次式の積に因数分解することと等価である。しかし、展開は機械的に行う方法があるのに対して、整式を因数分解する統一的な方法はないため、状況に応じて適当な方法を適用する必要がある。

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

=== 解の公式の利用 ===
'''[[二次方程式の解の公式]]'''により、''{{Mvar|ax}}''<sup>2</sup> + ''{{Mvar|bx}}'' + ''{{Mvar|c}}'' = 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>
と因数分解される。

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

=== 2数の和と積 ===
{{main|根と係数の関係}}
(''{{Mvar|x}}'' &minus; &alpha;)(''{{Mvar|x}}'' &minus; &beta;) = ''{{Mvar|x}}''<sup>2</sup> &minus; (&alpha; + &beta;)''{{Mvar|x}}'' + &alpha;&beta; という展開を逆向きに使う。''{{Mvar|x}}'' の項の係数と定数項から2数を見つける方法である。

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

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

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

 <math>\begin{matrix} 3 & & 2 & \longrightarrow & 4 \\  & \times & & & \\ 2 & & -1 & \longrightarrow & -3\end{matrix}</math>

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

=== 因数定理の利用 ===
{{main|因数定理}}
因数定理を利用する。すなわち ''{{Mvar|f}}''(''{{Mvar|x}}'') の値を 0 にする ''{{Mvar|x}}'' の値（[[冪根|根]]）を見つける。''{{Mvar|f}}''(&alpha;) = 0 となったとすれば、''{{Mvar|x}}'' &minus; &alpha; が ''{{Mvar|f}}''(''{{Mvar|x}}'') の因数の1つである。

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

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

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

; 注意: 零でも単元でもない元を「既約元」の積に分解するような因子分解を「既約元分解」と呼び、「素元」の積に分解されるとき「素元分解」と呼ぶ。素元は必ず既約元であったから素元分解は既約元分解の一種であるが、実はその分解は一意である{{efn|ゆえに、素元分解可能な整域（素元分解整域）は一意分解整域であるが、一意分解整域において素元は既約元だから、これらは実は同義である}}、しかし必ずしも逆（「既約元が必ず素元となる」という性質）は言えないから素元分解でない既約元分解を持つ整域は存在する（これは一意分解可能性質のうち、分解可能よりも一意性の方が困難な性質であることを含意している）。一般に、既約元分解可能な整域は{{ill2|原子整域|en|atomic domain}} ('''AD''')<ref>[https://arxiv.hatenablog.com/entry/2016/09/27/160000#fn-ac027e7c arXiv探訪 2016-09-27 22.一意分解整域]（個人ブログ）</ref>あるいは分解整域 (factorization domain<ref>{{citation|format=PDF|url=http://alpha.math.uga.edu/~pete/factorization2010.pdf|title=FACTORIZATION IN INTEGRAL  DOMAINS |author=PETE L. CLARK}}. p. 9. note. 5 も参照.</ref>; '''FD''') と呼ばれる。一方、「既約元が必ず素元となる」という性質は[[ユークリッドの補題]]と呼ばれ（これは {{mathbf|Z}} の既約元として定義される[[素数]]が {{mathbf|Z}} の[[素元]]であることを述べたユークリッドによる補題に名称を因む）、ユークリッドの補題を満たす整域をEL整域 (ELD) と呼ぶ。明らかに、ELDかつADなる整域において既約元分解は素元分解であり、したがって一意分解である。

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

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

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

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

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

{{ill2|論理行列|en|logical matrix}}は[[二項関係]]を[[表現 (数学)|表現]]するもので、[[行列の積]]が[[関係の合成]]に対応する。論理行列の分解を通して関係を分解することは、{{ill2|difunctional関係|en|difunctional}}のような関係の特質 (nature) の輪郭 (profile) を供与するものである。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{notelist}}
=== 出典 ===
{{reflist}}

== 関連項目 ==
* [[分解]]
* [[算術の基本定理]]
* [[一意分解環]]
* [[素因数分解]]
* [[多項式の因数分解]]
* [[多項式の根]]
* [[平方完成]]
* [[代数学の基本定理]]
* {{ill2|モノイドの分解|en|Monoid factorisation}}
* {{ill2|自然数の乗法的分割|en|Multiplicative partition}}: [[自然数の分割|自然数の（加法的）分割]]の乗法版

== 外部リンク ==
* {{MathWorld|urlname=Factorization|title=Factorization}}
* {{ProofWiki|urlname=Definition:Divisor_(Algebra)/Factorization|title=Definition:Divisor_(Algebra)/Factorization}}

{{Normdaten}}
{{DEFAULTSORT:いんすうふんかい}}
[[Category:多項式]]
[[Category:初等数学]]
[[Category:数学に関する記事]]