因数分解
算術の基本定理により、任意の正の整数は一意的な素因数分解を持つ。整数の因数分解アルゴリズムが与えられたとき、そのアルゴリズムを繰り返し適用して、任意の整数をその構成要素である素数にまで分解しきることができる。しかし、非常に巨大な整数に対して効率のよいアルゴリズムは知られていない。
2次式を因数分解するときに用いられる、たすきがけとよばれる方法がある。途中計算に引くバツ印の線をたすきの背中側から見た姿になぞらえた名前である。x の項の係数の正の約数と定数項の約数を組み合わせて x の項の係数を作る。
たとえば 6x + x − 2 を因数分解することを考える。x の項の係数 6 の正の約数と定数項 −2 の約数の組み合わせのうち、次のような組み合わせを選ぶ。
この計算で得られた 4 と −3 の和が x の項の係数1と等しいので、× の上の行の数 3 と 2 を使って 3x + 2 という式と作り、同様に下の行の数 2 と −1 を使って 2x − 1 という式を作る。このとき、元の2次式 6x + x − 2 はこの2つの式をかけ合わせることで求められるので、6x + x − 2 = (3x + 2)(2x − 1) という因数分解の結果を得る。
有理数係数の多項式環における既約因子分解には、効果的な計算機アルゴリズムが存在している。
一般の抽象代数学において、一意分解性質を持つ可換環は一意分解環 (UFD) と呼ばれる。ある種の数体系、例えば代数体の整数環(代数的整数環)の中には一意分解性質を持たないものが存在するが、これら代数的整数環の場合には幸いなことに、より弱い形での一意分解性質(任意のイデアルが素イデアルの積に一意的に分解される)を満足するデデキント環となる。一般に、既約元分解を持つ(が、一意分解とは限らない)整域を原子整域(英語版)または分解整域と呼ぶ。
より一般の数学的対象の中にも(より単純な対象からなる)積の形に書き表すことを一般に因子分解あるいは分解と言い表すものがある。たとえば、写像の分解とは特定の性質を持つ写像の合成の形に書き表すことである。任意の写像は全射と単射の合成として標準的な分解を持つ(これは圏論において、射の分解系・弱分解系(英語版)として一般化される)。また例えば、行列の分解とは、与えられた行列を特定の性質を持つ行列を用いて行列の積として書き表すことである。任意の行列は対角成分がすべて 1 の下三角行列 L と上三角行列 U および 置換行列 P の積に分解される(LUP分解: 実はこれはガウスの消去法を行列の形にまとめたものである)。